2015-07-04

# Problem 061: Cyclical figurate numbers

Description:

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

``````Triangle        P3,n=n(n+1)/2    1, 3, 6, 10, 15, ...
Square          P4,n=n2          1, 4, 9, 16, 25, ...
Pentagonal      P5,n=n(3n?1)/2   1, 5, 12, 22, 35, ...
Hexagonal       P6,n=n(2n?1)     1, 6, 15, 28, 45, ...
Heptagonal      P7,n=n(5n?3)/2   1, 7, 18, 34, 55, ...
Octagonal       P8,n=n(3n?2)     1, 8, 21, 40, 65, ...``````

The ordered set of three 4-digit numbers: `8128, 2882, 8281`, has three interesting properties.

• The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
• Each polygonal type: triangle (`P(3,127)=8128`), square (`P(4,91)=8281`), and pentagonal (`P(5,44)=2882`), is represented by a different number in the set.
• This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

Solution:
v\$\$  ### ---------------------------------------------------------------- ###
\$\$  ### ---------------------------------------------------------------- ###
\$   ### ---------------------------------------------------------------- ###
\$   ### ---------------------------------------------------------------- ###
\$   ### ---------------------------------------------------------------- ###
### ---------------------------------------------------------------- ###
### ---------------------------------------------------------------- ###
### ---------------------------------------------------------------- ###
### ---------------------------------------------------------------- ###
### ---------------------------------------------------------------- ###
### ---------------------------------------------------------------- ###
### ---------------------------------------------------------------- ###
v_v#!          _v#                       <1      g02\$\$<
#####    1 v  p02g01_v#! #  g02\$_v#!:p\+9%*88g02 <0
> # 6 # 10p   288** 20p>20g1-20p10g>1-:0\2*20g88*/+^^ \$<0p03+1g03 p+*2g02/*88g<
#####    0 >20g1-20p030p0>1+::::*\-2/20g1+*+:"}"8*\`#^_:"ec"*`#^_30g88*%9+30^
>g>1-:0\5\p:0\6\p:0\7\p:#v_\$  01-60p011p v
v<         \$_^#!:                   <0              <     <       <\$\$<
>611gg1+611gp611gg12p511gg13p12g10g-!#v_13g"_ "+`#v_712gg#^_13g88* %9+13g88*/12v
^<pg115+1gg115pg116-10                <v88g-1g115+9%*88g-1g115g11_^#g41p41g+*2g<
^<pgg11670p11-1g11                     *#        \$<v05+9%*8        8g05%"d"g41<
>/611g1-g2*+g"d"%14g"d"/-*#^_10g1-11g`!|
^<pg1150pg116-10p11+1g11pg2171                                                <
>2*+g:.+55+,21g1+:21p10g-#v_" =  ",,,,.@           >88*/60g2*+g"d"/-#^_v
^gg126/*88gg125+9%*88gg125<0p120                                       <
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

Pretty cool problem, I have to say.

It's one of these problem that you can easily make dynamic. In the middle-left of this program you see the number `6` surrounded with `#`. This is the "amount of resulting numbers" parameter of our program. For this Euler-problem you need to set this to `6`. But for debugging purposes I mostly tested it with `3`. And if you want you can try it out with bigger numbers `7` or `8`. (But then you need to move the code down a bit - otherwise the cache-part will intersect with the code-part).

With this number we first generate all the polygon-numbers from `3` to `SIDES_COUNT + 2` with the formula `(n-2) * (n^2 - n)/2 + n`. Then we go recursively through all these numbers. First we test triangle with square, then with square and so on. (The recursion is - as always - just a stack and a stack pointer).

A last note: This was (until now) probably the hardest program to fit in the befunge 80x25 size restriction. I barely managed to get it (and now its exactly 80x25) and I had to use quite some trickery.

 Interpreter steps: 50 105 245 Execution time (BefunExec): 14s (3.48 MHz) Program size: 80 x 25 (fully conform befunge-93) Solution: 28684 Solved at: 2015-07-04

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript