Cyclical figurate numbers
Problem 061: Cyclical figurate numbers
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# <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 <
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[1] with square[1], then with square[2] 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 |