# Project Euler#61: Cyclical figurate numbers

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

$$\begin{array}{lll} \textrm{Triangle} & P_{3,n}=n(n+1)/2 & 1, 3, 6, 10, 15, \ldots\\ \textrm{Square} & P_{4,n}=n^2 & 1, 4, 9, 16, 25, \ldots\\ \textrm{Pentagonal} & P_{5,n}=n(3n−1)/2 & 1, 5, 12, 22, 35, \ldots\\ \textrm{Hexagonal} & P_{6,n}=n(2n−1) & 1, 6, 15, 28, 45, \ldots\\ \textrm{Heptagonal} & P_{7,n}=n(5n−3)/2 & 1, 7, 18, 34, 55, \ldots\\ \textrm{Octagonal} & P_{8,n}=n(3n−2) & 1, 8, 21, 40, 65, \ldots \end{array}$$

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

1. 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).
2. 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.
3. 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.

While revising my previous solutions to bound under 5 seconds (because this is the most logical limit for any project Euler solution, otherwise the algorithm is flawed or not the best) I came to this which runs in around 10-15 seconds (peak at 12).

I have tried to make it better but I can't think of any remarkable improvements yet.

    static Stack<Integer> figurateStack;

public static int get61() {
figurateStack = new Stack<Integer>();
int count = -1;
int i = 1111;// minimum
final int n = 6;
final int low_lim = 3;
int[] a = new int[n];
boolean flag = false;// flag to use as a stepback conjugate
boolean stepback = false;
do {
flag = false;
if (count < n - 2) {
for (; i < 9999; i++) {
if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
if (count == -1 || (count >= 0 && i / 100 == a[count] % 100) && i > 1000) {
++count;
a[count] = i;
break;
} else {
figurateStack.pop();
}
}
}
} else {
i = (i % 100) * 100 + a / 100;
if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
++count;
a[count] = i;
break;
} else {
stepback = true;
}
}
if (i == 9999) {
stepback = true;
}
if (stepback) {
figurateStack.pop();
i = a[count] + 1;
--count;
flag = true;
stepback = false;
}
if (count < n - 2 && !flag) {
i = 100 * (i % 100) + 10;
flag = false;
}
} while (count < 6);
return a + a + a + a + a + a;
}

public static boolean isSpecialFigurate(int x, int lowlim, int upplim) {
for (int index = lowlim; index <= upplim; index++) {
if (!figurateStack.contains(index)) {
long n = (long) Math.floor((Math.sqrt(8 * (index - 2) * x + (index - 4) * (index - 4)) + (index - 4)) / (2 * (index - 2)));
if (getFigurateNumbers(n, index) == x) {
figurateStack.push(index);
return true;
}
}
}
return false;
}

public static long getFigurateNumbers(long n, int r) {
return (n * n * (r - 2) - n * (r - 4)) / 2;
}

• @200_success thankyou so much * bows * Jun 17, 2015 at 8:56
• You can avoid a lot of unnecessary work if you don't generate lots of useless numbers in order to push them through expensive filters; you can get away with generating each number just once, directly from its respective formula. Can't say much more than that - except perhaps for the word 'bitmask' - without spelling out the whole solution and robbing you of the amazing buzz of discovery... Feb 17, 2016 at 16:35

boolean flag = false;//FLAG flag to use as a stepback conjugate
boolean stepback = false;
do {
flag = false;//FLAG
if (count < n - 2) {
for (; i < 9999; i++) {
if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
if (count == -1 || (count >= 0 && i / 100 == a[count] % 100) && i > 1000) {
++count;
a[count] = i;
break;
} else {
figurateStack.pop();
}
}
}
} else {
i = (i % 100) * 100 + a / 100;
if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
++count;
a[count] = i;
break;
} else {
stepback = true;
}
}
if (i == 9999) {
stepback = true;
}
if (stepback) {
figurateStack.pop();
i = a[count] + 1;
--count;
flag = true;//FLAG
stepback = false;
}
if (count < n - 2 && !flag) {//FLAG
i = 100 * (i % 100) + 10;
flag = false;//FLAG
}
} while (count < 6);
return a + a + a + a + a + a;


You've got a flag variable in there. But from what I see, you don't need it. I've labeled all the usages with //FLAG.

The only line that sets flag to true is inside the if statement stepback. stepback is triggered by i == 9999 or some other condition earlier.

flag is set to false at the top of your do-while loop. So every iteration, it's set to false.

Because of this, the flag variable cannot be changed from false until the stepback if-statement.

So we can do this:

    if (stepback) {
figurateStack.pop();
i = a[count] + 1;
--count;
flag = true;//FLAG
stepback = false;
} else if (count < n - 2) {
i = 100 * (i % 100) + 10;
flag = false;//FLAG
}


if stepback occured, flag is true, and the if statement thereafter becomes always false. So turn it into an else.

You don't make any other checks for flag, so now flag can be removed.

boolean stepback = false;
do {
if (count < n - 2) {
for (; i < 9999; i++) {
if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
if (count == -1 || (count >= 0 && i / 100 == a[count] % 100) && i > 1000) {
++count;
a[count] = i;
break;
} else {
figurateStack.pop();
}
}
}
} else {
i = (i % 100) * 100 + a / 100;
if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
++count;
a[count] = i;
break;
} else {
stepback = true;
}
}
if (i == 9999) {
stepback = true;
}
if (stepback) {
figurateStack.pop();
i = a[count] + 1;
--count;
stepback = false;
} else if (count < n - 2) {
i = 100 * (i % 100) + 10;
}
} while (count < 6);
return a + a + a + a + a + a;


Next, we can collapse the if statement i == 9999 to be included in the stepback check:

    if (i == 9999) {
stepback = true;
}
if (stepback) {


We just do

    if (stepback || i == 9999) {


Because stepback disables itself, we don't need to worry about previous iterations of the while loop having stepback = true.

There's also an explicit else that we can make implicit...

        if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
++count;
a[count] = i;
break;
} else {
stepback = true;
}


to

        if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
++count;
a[count] = i;
break;
}
stepback = true;


Making the total code

boolean stepback = false;
do {
if (count < n - 2) {
for (; i < 9999; i++) {
if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
if (count == -1 || (count >= 0 && i / 100 == a[count] % 100) && i > 1000) {
++count;
a[count] = i;
break;
} else {
figurateStack.pop();
}
}
}
} else {
i = (i % 100) * 100 + a / 100;
if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
++count;
a[count] = i;
break;
}
stepback = true;
}
if (stepback || i == 9999) {
figurateStack.pop();
i = a[count] + 1;
--count;
stepback = false;
} else if (count < n - 2) {
i = 100 * (i % 100) + 10;
}
} while (count < 6);
return a + a + a + a + a + a;

• Your code still uses the same generate-everything-and-apply-expensive-filters approach as the original code, which involves quite a bit of unnecessary/repeated work. Do your micro-optimisations make the code fast enough to meet ADG's target? Feb 17, 2016 at 15:26
• I... didn't check, and most likely they wont. I didn't spot the correct solution, but thought my points were at least valid as cleanup / micro-optimizations. Feb 17, 2016 at 17:47
• The points that you raised in your article are valid indeed, and I did not mean to belittle your work in any way (I know only too well how difficult it is to hone a non-trivial piece of someone else's code to make it leaner and meaner, to take it closer to its true essence). I was just curious about the result... You didn't mention it and my skills regarding mental execution of Java code are woefully inadequate for the task. I guess other readers might wonder, too, given that ADG explicitly mentioned 5 seconds. BTW - Kudos to ADG for the 're-Euler with time limit' thing. That's the spirit! Feb 17, 2016 at 18:26