Excellent Numbers
March 24, 2015
1: 48
2: 3468
3: 140400 190476 216513 300625 334668
416768 484848 530901 641025 871276
4: 16604400 33346668 59809776
5: 3333466668 4848484848 4989086476
6: 101420334225 181090462476 238580543600 243970550901
268234583253 274016590848 320166650133 333334666668
346834683468 400084748433 440750796876 502016868353
569466945388 620741003025 743091138101 754361150400
7: 33333346666668 48484848484848
8: 1045751633986928 1140820035650625 3333333466666668
6317486101531025 9607843137254901 9988116741295308
9: 103495840337945601 115220484358463728 134171310390093900
139601140398860400 140400140400140400 146198830409356725
168654484443958128 189525190474810476 190476190476190476
215488216511784513 216513216513216513 225789700526090001
241951680548171776 271851166588008693 299376300623700625
300625300625300625 332001666665001333 333333334666666668
334668334668334668 344329484680361873 415233416766584768
416768416768416768 468197520829099776 483153484846516848
484848484848484848 529100530899470901 530901530901530901
572945416949321793 624431451007147500 638976641023361025
641025641025641025 655251971041444725 747278381142673776
782233361180729601 846197267249898828 868725871274131276
871276871276871276 956420535367903788
10: 21733880705143685100 22847252005297850625 23037747345324014028
23921499005444619376 24981063345587629068 26396551105776186476
31698125906461101900 33333333346666666668 34683468346834683468
35020266906876369525 36160444847016852753 36412684107047802476
46399675808241903600 46401324208242096401 48179452108449381525
64626742850314693488 64997454310355874901 67232333010603499376
Mm. b*b – a*a = n. Rewriting n to be a*100000 + b, yields b * b – b == a * (a + 100000). Which can be reduced to b = ((4*a**2+400000*a+1)**0.5+1) / 2. So we loop through all a values with 5 digits to find b and see if b is an integer. In Python:
Or in one line (rewriting b):
Both result in 13171037992
In Python. Same as Rutger’s. The first part of the number a needs to be even. I think, there should be a check that b is not too large. For n=10 this never happens, but for n=12 it happens.
Strictly speaking, you probably ought to check that b isn’t an integer because it’s missing low bits.
That is, if b is an integer, make sure it’s actually a solution.
We want solutions to a*(a+10000) = b*(b-1), both sides are monotonic, so we can just scan up through the two sequences, looking for common elements (not too far from the merge problem the other day).
We can optimize this of course (eg. a must be even and b can be initialized to 1000 as well, also various strength reductions are possible).
A little bit of pencil and paper work will show that the last digit of b(b-1) can only be 0,2, or 6. Consequently,
a must end in 0, 4, or 6. That eliminates 70% of the numbers that must be tested.
@Ernie: good point, also b is 4k or 4k+1.
Another approach:, we can use the quadratic Diophantine equation solver (and it’s methods) at http://www.alpertron.com.ar/QUAD.HTM to solve x^2 – y^2 +10000x +1 = 0, which reduces the problem to finding x’ and y’ that satisfy (x’ + y’)(x’ – y’) = 9999999999
Here’s the divisors approach coded up, seems to work though I haven’t proved it correct. I don’t understand why a should be even and b should be odd, though that always seems to be the case.
The equation is a^2 – b^2 + 100000a + b = 0, we substitute x = 2a+100000 and y = 2b-1, and as above, the equation then simplifies to (x+y)(x-y) = 9999999999. It’s very similar to the torn numbers problem of a few weeks ago and like there, a more intelligent generation of all divisors would be possible:
Incidentally, I don’t think all the numbers on the page 3 list are right, for example 620741003025 is lacking in excellence. Maybe you need a range check for b?
I’ve gone a bit crazy on this problem and have almost completed the list of 30-digit excellent numbers, along with some proofs about the interesting patterns in them. As someone pointed out, the list of numbers presented here has several errors. You can see more at excellent nums.com.
I’ll double you: 617972744134287544096427144466999931525969228137094506182988
In fact, with the help of http://www.numberempire.com/numberfactorizer.php and http://wpedia.goo.ne.jp/enwiki/User:Toshio_Yamaguchi/Factorizations_of_POTPO_numbers, it’s not too hard to factorize 10^160-1 as [3, 3, 11, 17, 41, 73, 101, 137, 271, 353, 449, 641, 1409, 3541, 9091, 27961, 69857, 1634881, 1676321, 5070721, 5882353, 18453761, 947147262401, 117633133855156294075039863860622161, 349954396040122577928041596214187605761], and once we have that, we can find (with a version of my python program up above) eg:
3016693653810692443471528771919068734283766879102218756224920866230260139596321662663687362816936566086878697389529438778910186253288857357094019024639046138113
along with another 153843 most excellent 160-digit numbers.
Thanks to this excellent website, http://stdkmd.com/nrr/repunit/, we can now go to 2016 digits, for example:
[…] number n, with an even number of digits, is excellent if it can be split into two halves, a and b, such that b2 – a2 = n. Let 2k be the number of digits, […]
I was going to add a link to my blog post working out the divisors solution properly, but WordPress seems to have done that for me.
One curious fact: after sorting the numbers produced lexicographically, the largest that came up was:
618033865994856576190462466045494275576755186660999999862755693037993862789961848095236722795025
Looks like we are converging on the Golden Ratio!