## 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!