<< problem 124 - Ordered radicals | Repunit divisibility - problem 129 >> |

# Problem 125: Palindromic sums

(see projecteuler.net/problem=125)

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2.

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is 4164.

Note that 1 = 0^2 + 1^2 has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than 108 that are both palindromic and can be written as the sum of consecutive squares.

# Algorithm

My function `isPalindrome`

determines whether it's parameter is a palindrome or not:

- iteratively remove the lowest digit and append it to `reverse`

- if at the end `reverse == x`

then we have a palindrome

A small optimization is to check the right-most digit for zero because then it can't be a palindrome.

Two nested loops iterate over all possible sequences.

My first solution wasn't correct because I didn't notice that sums may appear multipe times (there are two "collisions" for the original problem).

All palindromes are temporarily stored in `solutions`

and then I remove all duplicates (see oeis.org/A267600).

## Alternative Approaches

There is a closed formula for a sequence \sum_{a=i..j}{a^2} but I'm not sure whether it would be faster because my incremental computation of `current`

is extremely efficient.

## Modifications by HackerRank

The upper limit can be defined as well as the distance between consecutive "numbers" (what I call `stride`

):

instead of a^2 + (a+1)^2 + (a+2)^2 + ... the terms are a^2 + (a+stride)^2 + (a+2 * stride)^2 + ...

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <vector>
#include <iostream>
#include <algorithm>
// return true if x is a palindrome

bool isPalindrome(unsigned int x)
{
auto reduced = x / 10;
auto reverse = x % 10;
// fast exit: a trailing zero can't create a palindrome
if (reverse == 0)
return false;
while (reduced > 0)
{
// chop off the lowest digit and append it to "reverse"
reverse *= 10;
reverse += reduced % 10;
reduced /= 10;
}
// palindrome ? both must be equal
return reverse == x;
}
int main()
{
unsigned int tests = 1;
std::cin >> tests;
while (tests--)
{
unsigned int limit = 100000000;
unsigned int stride = 1; // distance between consecutive square numbers
std::cin >> limit >> stride;
std::vector<unsigned int> solutions;
for (unsigned long long first = 1; 2*first*first < limit; first++)
{
auto next = first + stride;
// sum of a^2 + b^2 + ...
auto current = first * first + next * next;
// still within the limit ?
while (current < limit)
{
// check
if (isPalindrome(current))
solutions.push_back(current);
// add one element to the sequence
next += stride;
current += next * next;
}
}
// sort ...
std::sort(solutions.begin(), solutions.end());
// .. and remove duplicates
auto garbage = std::unique(solutions.begin(), solutions.end());
solutions.erase(garbage, solutions.end());
// count all solutions
unsigned long long sum = 0;
for (auto x : solutions)
sum += x;
std::cout << sum << std::endl;
}
return 0;
}

This solution contains 12 empty lines, 11 comments and 3 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This is equivalent to`echo "1 1000 1" | ./125`

Output:

*Note:* the original problem's input `100000000 1`

__cannot__ be entered

because just copying results is a soft skill reserved for idiots.

*(this interactive test is still under development, computations will be aborted after one second)*

# Benchmark

The correct solution to the original Project Euler problem was found in **less than 0.01** seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

May 17, 2017 submitted solution

May 17, 2017 added comments

# Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler125

My code solved **35** out of **35** test cases (score: **100%**)

# Difficulty

Project Euler ranks this problem at **25%** (out of 100%).

Hackerrank describes this problem as **easy**.

*Note:*

Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.

In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is never an option.

# Links

projecteuler.net/thread=125 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

Python: www.mathblog.dk/project-euler-125-square-sums-palindromic/ (written by Kristian Edlund)

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p125.java (written by Nayuki)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are already solved and there wasn't a Hackerrank version of it (at the time I solved it) or I didn't care about it because it differed too much.

*Please click on a problem's number to open my solution to that problem:*

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

<< problem 124 - Ordered radicals | Repunit divisibility - problem 129 >> |