Source

project-euler / project-euler / 40.txt

Full commit
d[1] = 1

123456789

d[10] = 1

10,11,12,13,14,...
^
|
10
   12 14 16

10+90/2 = 55

d[100] = 5

------------------

End of the two-digits (first digit of 100):

(99-10+1)*2 + 10 = 190

100,101,102,103,104
^
190 ^
    193 ^
        196

100 + (1000-190)/3 = 100 + 810/3 = 100 + 270 = 370

d[1000] = 3

-------------------------

End of the three digits (first digit of 1000):

(999-100+1)*3 + 190 = 900*3 + 190 = 2700 + 190 = 2890

1000,1001,1002

^
2890 ^
     2894 ^
          2898

1000+(10,000-2890)/4 = 3500 - 2890/4 = 3500 - 700 - 90/4 = 2800 - 90/4 = 
2800 - 22 - 2/4 = 2800-23+2/4 = 2777+2/4

d[10,000] = 7

--------------------------------------

End of the four digits (first digit of 10,000):

(9,999-1,000+1)*4 + 2,890 = 9,000*4+2,890 = 36,000 + 2,890 = 38,890

10,000 ; 10,001 ; 10,002 ; 10,003

^
38,890   ^
         38,895   ^
                  38,900

10,000 + (100,000 - 38,890)/5 = 10,000 + 20,000 - 3,889 * 2 = 
30,000 - 3,900 * 2 + 2*11 = 30,000 - 7,800 + 22 = 22,200 + 22 = 22,222

d[100,000] = 2

-------------------

End of the five digits (first digit of 100,000):

(99,999 - 10,000+1)*5 + 38,890 = 90,000*5 + 38,890 = 450,000 + 38,890 =
488,890

100,000 ; 100,001 ; 100,002 ; 100,003

^
488,890   ^
          488,896   ^
                    488,902

100,000 + (1,000,000 - 488,890)/6 = 100,000 + 511,110/6
>>>>
     85,185  
    --------
    511,110|6
    48
    --
     31
     30
     --
      1,1
        6
      ---
        51
        48
        --
         30
<<<<

100,000 + 85,185  = 185,185

d[1,000,000] = 1