Amicable chains
Problem 095: Amicable chains
The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.
Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.
Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:
12496 -> r -> 15472 -> 14536 -> 14264 (-> 12496 -> ...)Since this chain returns to its starting point, it is called an amicable chain.
Find the smallest member of the longest amicable chain with no element exceeding one million.
Solution:
X # ## ## ## ##
XXX #
XX # . . . .
X # . . . .
X # . . . .
# . . . .
#
# ## .... ## ## .... ##
CCC # ## ## ## ##
>"}"8*19p"q"9*29p"}}@"**39p012p014p39g15p39g>1-:0\:19g/9+\19g%p v
v < |:p%g91\+g92/g91:\0:<
1 v+1p%g91\+g92 /g91:\+g31g%g91\+g92/g91 ::<
>:13p2>:13g*:39g\`#^ #$ #< |
^_$# 6# v# -g93:+1$$< vp51g\7:<
v < >v>g+\19g%g22pv >v >v >v > v
> :23p :19g/9+\19g%g!|> 23g:70p11v >22g:0`|>:39g\`|>:23g-|$ >:7\g22g-| # > 32g14p:7\g15pv
| -g93:+1 g32 < $< < <0 ^ < >131p:12g\-32p32g14g`||*g13`\g51g\7:<
>$15g.@ ^92/g91:p2< ^p22g%g< >31p032p0^ < v
>9g%p22g:19g/29g+\19^ v< |-g21:+1 < <
^ < <|g13$< <
^1\+9/g91:\1pp21+1:g217:g22<_^#!g%g91\+9/g91:g22<
Explanation:
The trick is to use a sieve to pre-calculate all the proper-divisor-sums.
We use a big 1000x1000 array to store all the proper-divisor-sums of all numbers from one to one million.
Initially we set all these fields to zero, then we add 1 to all multiples of 1, the 2 to all multiples to 2 etc, etc.
At the end we have a nice map of all the interesting numbers. (Fun fact: we have also calculated the primes, every number for which the sum is 1 is prime).
Then we use a second 1000x1000 array to remember the values we have already checked. The rest is simply iterating through all the numbers, trying to build a chain for each one and remembering the length of the longest chain together with its smallest member. While doing this we track the visited values in our cache array to prevent checking the same chain multiple times.
This code is not the fastest in befunge, but I honestly can't see a way to gain big performance (the same code in C# runs in 107ms). Most of the time is spend with building the map of the amicable values, but all approaches with calculating them on-demand where way worse than this algorithm.
| Interpreter steps: | 1 053 466 251 |
| Execution time (BefunExec): | 4min 2s (4.34 MHz) |
| Program size: | 2017 x 1035 |
| Solution: | 14316 |
| Solved at: | 2016-09-18 |