Subscribe via feed.

Smallest Square Number

Posted by Karl Sharman on June 27, 2011 – 4:51 am

A “twin number” is a number formed by writing the same number twice, for instance, 88, 2222 or 1596315963 etc.

What is the smallest square twin of an integer?

To help you on your way…. it isn’t 11.

Tags:
This post is under “Tom” and has 28 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

28 Responds so far- Add one»

  1. 1. DP Said:

    Karl, are you looking for something like: xyz^2 = xyzxyz ? Beacause I don’t think that exists…
    9^2 = 81
    99^2 = 9801
    999^2 = 998001
    9999^2 = 99980001
    and so on

    we can never reach 9999…^2 = 9999…9999… or by using anything less than 9s

    If you are just looking for a twin number that is a perfect square of an integer that doesn’t necessarily have the same digits I still can’t help you. My scientific calculator can’t do that many digits. So a hint to others tackling this one, we’re looking for a pretty large number. Might need that big caluclator online. I think Chris has posted several links to it in past problems.

  2. 2. Karl Sharman Said:

    DP – for clarification – it is only the product that is a “twin” number that I am looking for.

    The calculating website is Wolfram Alpha – http://www.wolframalpha.com

  3. 3. John24 Said:

    2 would yield 44 but your 11 leads me to believe this is not what you are looking for.

    Are we supposed to find a number which when squared and the result appended to itself is also a perfect square?
    13 = 169169 and the square root of 169169 needs to be an integer?

    If so, simple brute force should get us there in a few years.

  4. 4. 88*88=7744 Said:

    I didn’t need to calculate too long, since it was only a 2-digit number.

  5. 5. Chris Said:

    I think Karl wants something like xyzxyz = m². m needn’t be anything special. i.e. we want to find a twin number that is also a perfect square. I can’t see why that wouldn’t be possible, but it will involve number crunching. I suspect the number sought is quite large (having had a quick dip in this water).

    Wolframalpha has a useful function, “fator(n)” which will return the prime factors of an integer n. It corresponds to the Mathematica function “FactorInteger” (which wolframalpha also accepts).
    e.g. http://www.wolframalpha.com/input/?i=factor%2854%29

  6. 6. Chris Said:

    Hi 88*88=7744. I doubt that’s what Karl is looking for. In fact, I’m not really clear what Karl is looking for:(

  7. 7. Karl Sharman Said:

    Chris, you were right in your first sentence of post 5.
    Any number (n) ^2 = the twin number we are looking for

  8. 8. Eketahuna Said:

    I’ve checked up to 1,000,000,000 as a base number and the closet I have got is a base number of 2,445,865 which yields 5982255598225. There are a few that get close like this (e.g. 309,097 = 95540955409) but I can’t spare any more CPU. Oh for the days when I had unlimited access to a good old mainframe !

  9. 9. Chris Said:

    Hi Eketahuna. I’ve checked much larger numbers than that.

    Hi Karl. Thanks for the confirmation. I assume that padding 0’s aren’t allowed.

    Needless to say, I’m about to inroduce modulo arithmetic into it. My first stab shows that no such number exists.

  10. 10. Chris Said:

    On wolframaplpha you must use FactorInteger(n) for large integers.

  11. 11. Eketahuna Said:

    Hi Chris, I stopped there as I thought if it was any larger it would take too long to find it, if it exists. As nothing shows up that far, I’m inclined to also believe that no such number exists. This is, after al ToM and we could spend a fair amount of time looking for nothing (assuming, as you say padding 0’s are not allowed, so 0 as the base number is discounted).

  12. 12. Chris Said:

    If leading 0’s are allowed then
    00 826 446 281 00 826 446 281 = 9090909091² is your man.

    I’m pretty sure that it can’t be done without leading 0’s being involved.

    I’ll delay publishing how I got that result and my proof that it cannot be done without leading 0’s for a while.
    No doubt Karl will show me that I’m wrong now I’ve committed myself :(

  13. 13. Chelsea Said:

    Is it 1.1? 1.1 * 1.1 = 1.21

  14. 14. Chris Said:

    I’m going for 13223140496 13223140496 = 36363636364²

    Thanks to modulo arithmetic, no serious number crunching is actually required. I did use wolframalpha’s FactorInteger function :( but it wasn’t necessary.

  15. 15. Chris Said:

    The next few square twins are:

    20661157025 20661157025 = 45454545455²
    29752066116 29752066116 = 54545454546²
    40495867769 40495867769 = 63636363637²
    52892561984 52892561984 = 72727272728²
    66942148761 66942148761 = 81818181819²
    82644628100 82644628100 = 90909090910²

    I’ve used a space to separate the two halves of each twin.

    So, folks, what’s the next group of such square twins?

    I have been a little incautious in claiming that heavy duty number crunching isn’t required. That is true, as long as you don’t require to find the groups of square twins in size order.

    Karl. Thanks for finding that one, yet again I’ve enjoyed exploring the strange world of modulo arithmetic with powers.

    Anyone who wants to work on this problem will find reading up on the Euler totient function worthwhile: http://en.wikipedia.org/wiki/Euler%27s_totient_function

  16. 16. Karl Sharman Said:

    I looked for a basic form of the “twin” numbers, which is:-
    some number a = 1 + 10^n multiplied by some number 10^(n-1) <= b < 10^n.

    If ba is a perfect square, a must have some repeated factor, since b < a.

    Searching the possible values of a for one with a repeated factor eventually turns up the number 1 + 10^11 = 11^2 * 826446281. This is where a Cadbury's Number Crunchie comes in useful…

    So, we get b=826446281 and ba = 9090909091^2 = 82644628100826446281, but this needs leading zeros to fit the pattern. As Chris noted – this is a no-no….

    So, we multiply by a suitable small square (tried 4 and 9 – no use, but 16…) to get
    1322314049613223140496 = 36363636364 ^ 2.

    I am not sure if this is legit maths, or whether I am adding in a few un-intuitive leaps to make an answer fit… but, it matches Chris's answer, so I'm happy…..

  17. 17. Chris Said:

    Hi Karl. I’m equally relieved that you concur with my answer. You’ll be pleased to hear that your method doesn’t raise my hackles ;)

    In fact you were more up front on tackling the leading 0’s than I was (at first).

    Sadly, because of the requirement of the smallest square twin, Cadbury’s Number Crunchie is a sensible tool.

    I will post my method (with some extras) later – it is surprisingly tedious to write up clearly. When we consider 1 + 10n as n increases, the first time we hit a squared factor, the factor is 11² and the next time it is 7². So the order isn’t a simple as we’d like.

    I’ve just noticed the link in my previous post was broken (now fixed), here it is again: http://en.wikipedia.org/wiki/Euler%27s_totient_function

  18. 18. John24 Said:

    Nice job Chris!

    I was looking for the wrong solution because I didn’t fully understand the question.

    Based upon your answers simple math should get you to the next perfect square twin.

    20661157025 20661157025 = 45454545455²
    29752066116 29752066116 = 54545454546²
    40495867769 40495867769 = 63636363637²
    52892561984 52892561984 = 72727272728²
    66942148761 66942148761 = 81818181819²
    82644628100 82644628100 = 90909090910²

    100000200002 10000020001 = 100000100001^2

    Add a 1 or subtract a 1 to every other digit. Add 1 to the far right digit and sub 1 from digit to the left and carry as needed. Repeat for all digits.

  19. 19. Chris Said:

    Hi John24. It took me a while to understand the question too.

    Do you know why that add/subtract 1 digit works? (It’s a mod 11 thing). I’m pretty sure that it won’t work with the next group of square twins as they’re based of 7² rather than 11²

  20. 20. Amit Neema Said:

    it can olny be 00 or 0000 so on….

  21. 21. Chris Said:

    Hi Amit, try reading the solutions offered. Come back in a few days; I’ll then have posted some theory about this problem.

  22. 22. Chris Said:

    Let N be a number string of length n. We want
    NN = m² = N(1 + 10n) e.g. N = 123 for the twin 123123.

    We need to find n such that 1 + 10n has a factor p².
    Let 1 + 10n = kp². Then Nkp² = m² and the obvious choice is to set N=kq² to get (kqp)² = m². q is required to eliminate leading 0’s.

    If p² is a factor of 1 + 10n, then 1 + 10n = 0 (mod p²) => 10n = -1 (mod p²). Although I’ll seem to be focusing on prime p, you must bear in mind that p could be composite.

    p cannot be 2 or 5 (or a multiple thereof) as 10n = 0 (mod 2 and 5). p cannot be a multiple of 3 as 10n = 1n = 1 (mod 3). The next candidate is p = 7. Then 10n = 3n (mod 7). We’d like to find 3n = -1 = 6 (mod 7). As 7 is prime, we can use Fermat’s little theorem (FLT) ap-1 = 1 (mod p), where p is prime and gcd(a,p) = 1 (fortunately gcd(10,p) = 1 for all prime p > 5). Clearly we need a(p-1)/2 = -1 (mod p), if we are to find a solution (that might not be quite true, but I’ll be more careful when I get to the next stage with φ). In this case, 3(7-1)/2 = 3³ = 6 = -1 as required (mod 7). But this is not enough, we have simply shown that 1001 is divisible by 7. We need to show that it is divisible by 7² = 49. But then we cannot use FLT. Fortunately Euler generalised FLT using his totient function, φ(m), to
    aφ(m) = 1 (mod m), where gcd(a,m) =1 and m is merely an integer (again gcd(10,p²) = 1 for all prime p >5). If m has prime factors a,b,c,…, and m = ai bj ck …, then φ(m) = m(1 – 1/a)(1 – 1/b)(1 – 1/c)(…). In particular, if p is prime, φ(p²) = p²(1 – 1/p) = p(p-1). For 49 we therefore have φ(49) = 7*6 = 42 (would you believe that). So 1042 = 1 (mod 49). Euler doesn’t guarantee that 42 is the smallest number that does the job. But it does guarantee that if there is a smaller number, then it must be a factor of 42. 42 = 2*3*7, so any of 2, 3, 6, 7, 14 or 21 might be sufficient. It happens that 42 is in fact the smallest value that works. It also happens that 1021 = -1 (mod 49). But it also happens that this corresponds to the second smallest group of square twins.

    p = 11 => p² = 121 => φ(121) = 11*10 = 110 => 10110 = 1 (mod 121). 110 = 2*5*11. So 2,5,10,11,22 or 55 might work too; and indeed, 22 actually works, and then we find that 1011 = -1 (mod 121) => n = 11, and this (fortunately) turns out to correspond to the smallest square twin. In particular we have 1 + 1011 = 121 * 826446281. So k = 826446281. But 826446281 is a 9 digit number and we need an 11 digit number. So we must multiply 826446281 by a square in the range 12.1 < q² < 121. So q² = 16,25,36,49,64,81 or 100 are possible. Hence we get the half twins, N, 13223140496, 20661157025, 29752066116, 40495867769, 52892561984, 66942148761 and 82644628100.

    For more on the totient function (including some amazing identities and properties) see: http://en.wikipedia.org/wiki/Euler%27s_totient_function

    I’m sorry the above analysis is not as clear as it could be. It takes a lot of effort to write this stuff up, and some is directly from my first stabs at doing this problem (sufficiently well to satisfy me that it’s all Kosher) – hence I looked at primes rather than their squares initially.

  23. 23. amirah Said:

    the number is 00

  24. 24. Karl Sharman Said:

    Amit Neema and amirah, 0^2, or the number 00, 0000 etc usually are represented by the figure 0. Just the way it is :-(

  25. 25. Chris Said:

    On divisibility by 11.

    If an n+1 digit decimal number N = Dn…D1D0 is divisible by 11, then (writing in reverse order) we have

    N = D0 + D1 10 + D2 102 + … + Dn 10n = 0 (mod 11)

    Using 10 = 11 -1 = -1 (mod 11), we get N = D0 – D1 + … (-1)nDn = 0 (mod 11)

    So starting with the units, we simply sum D0 – D1 + D2 – D3 + … ± Dn, where we just alternate the signs. If that adds to 0 (mod 11) then the original number is divisible by 11.

  26. 26. ASHISH JHA Said:

    Hello,Karl as far as i think one would not get a perfect square no. If i’ve understood this question clearly then the twin no. is 9999 and thus the integer would be 100 approx………

  27. 27. Karl Sharman Said:

    Hi Ashish, Chris got it right around post 14 – and explanations in depth follow in subsequent posts.

  28. 28. SJ Said:

    00? I havent a clue what you guys are doing?but a twin number ? id think that is 00 :L

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0