Depth-first search method for searching for all "superpalindromes" whose prime factors are all <=N

A question was asked over at math.SE (here) about whether or not there are infinitely many superpalindromes. I'm going to rephrase the definition to a more suitable one for coding purposes:


Definition: A superpalindrome is a product of primes p(1) p(2) ... p(k), where p(i)<=p(i+1) for 1<=i<=k-1, such that p(1) p(2) ... p(r) is a palindrome for all 1 <= r <= k.

A natural question to ask, is whether or not there's an infinite number of superpalindromes with all of its prime factors <=N. Thus, we can use a depth-first search.

Here is my implementation in C using GMP, but I'm wondering if there is some ways to give non-trivial run-time improvements.

```
#include
#include

// search for superpalindromes containing prime factors in {2,3,...,q}
// where q is the MAX_NR_PRIMES-th prime
#define MAX_NR_PRIMES 20000

#define MAX_SEARCH_DEPTH 100
#define MAX_NR_DIGITS 10000

// start backtracking at the (STARTING_PRIME_ID+1)-th prime
#define STARTING_PRIME_ID 0

mpz_t list_of_small_primes[MAX_NR_PRIMES];
mpz_t n_new[MAX_SEARCH_DEPTH];
int max_depth_reached=0;

mpz_t nr_superpalindromes_found[MAX_SEARCH_DEPTH];

// checks if n is a palindrome
// idea "borrowed" from http://gmplib.org/list-archives/gmp-discuss/2012-February/004876.html
int is_palindrome(mpz_t n) {
char m[MAX_NR_DIGITS];
int len=gmp_sprintf(m,"%Zd",n);
for(int i=0;i=i
// such that n*p is a palindrome; continues searching if one is found
int extend_superpalindrome_backtracking_algorithm(mpz_t n,int i,int depth) {
for(int i_new=i;i_newdepth+1 prime factors
if(depth>max_depth_reached) {
max_depth_reached=depth;
gmp_printf("superpalindrome found: %Zd at depth %d: ",n_new[depth],depth+1);
mpz_t primes[MAX_SEARCH_DEPTH];
for(int i=0;i<MAX_SEARCH_DEPTH;i++) mpz_init(primes[i]);
mpz_set(primes[0],n_new[0]);
for(int i=1;i<=depth;i++) mpz_divexact(primes[i],n_new[i],n_new[i-1]);
for(int i=0;i<=depth;i++) gmp_printf("%Zd ",primes[i]

Things you did well

-
You defined i within your for loops, and abided by the C99 standards.

-
You used an external library instead of writing your (more likely inefficient) own methods, and thus avoided unnecessarily reinventing-the-wheel.

Things you could improve on:

Efficiency:

-
Copying a whole number into a external array with gmp_sprintf() in your is_palindrome() method is very time consuming, as you suspected.

int is_palindrome(mpz_t n) {
  char m[MAX_NR_DIGITS];
  int len=gmp_sprintf(m,"%Zd",n);
  for(int i=0;i<len;i++) {
    if(m[i]!=m[len-i-1]) return 0;
  }
  return 1;
}

Is it reasonable to assume that most numbers will be non-palindromes? If not, I would suggest something like this:

-
Determine the approximate number of digits in your number a using
mpz_sizeinbase() and call this number \$ n \$.

-
Compute \$ \dfrac{a}{d^{(n-30)}} \$, then compute \$ a \bmod d^{30} \$. Print both in base \$ d \$ and compare. If they are unequal, reject as non-palindrome.

Computing \$ \dfrac{a}{d^{(n-30)}} \$ will be fast using mpz_tdiv_q().
Unfortunately, computing \$ d^{30} \$ is not fast. Perhaps a rough approximation of that would also increase efficiency.

-
Using a sieve for an early exit would increase efficiency.

-
Combine some of your for loops.

for(int i=0;i<MAX_SEARCH_DEPTH;i++) mpz_init(n_new[i]);
for(int i=0;i<MAX_SEARCH_DEPTH;i++) mpz_init(nr_superpalindromes_found[i]);
...
for(int i=1;i<=depth;i++) mpz_divexact(primes[i],n_new[i],n_new[i-1]);
for(int i=0;i<=depth;i++) gmp_printf("%Zd ",primes[i]);
...
for(int i=0;i<MAX_SEARCH_DEPTH;i++) mpz_init(primes[i]);
for(int i=0;i<MAX_SEARCH_DEPTH;i++) mpz_clear(primes[i]);

These loops are very similar, and many iterations (even for simple loops) can take more time than you think. Combining them will increase efficiency.

-
Try to avoid putting statements that print data to the console inside of a loop.

for(int i=0;i<=depth;i++) gmp_printf("%Zd ",primes[i]);

gmp_printf() (and all printf()-esque statements) can be very taxing on a system. Extracting them to the outside of the loop will increase efficiency.

Style:

-
Your code is very compact.

for(int i=0;i<MAX_SEARCH_DEPTH;i++) mpz_init(primes[i]);
mpz_set(primes[0],n_new[0]);
for(int i=1;i<=depth;i++) mpz_divexact(primes[i],n_new[i],n_new[i-1]);
for(int i=0;i<=depth;i++) gmp_printf("%Zd ",primes[i]);
printf("\n");
for(int i=0;i<MAX_SEARCH_DEPTH;i++) mpz_clear(primes[i]);

I'm all for compact code, but you still want your code to be readable. Let it breathe a bit. Use spaces after commas and semi-colons, use an empty line to separate and organize code.

-
You sometimes write a loop with braces, and sometimes without braces, even though they both have one statement in them.

for(int i=0;i<len;i++) {
  if(m[i]!=m[len-i-1]) return 0;
}
...
for(int i=0;i<MAX_SEARCH_DEPTH;i++) mpz_init(primes[i]);

Choose one way and stick with it. Consistency is very important.

Syntax

-
If you don't accept any parameters into a function, they should be declared void.

int main(void)

Comments:

-
You have some obsolete comments that can be removed (old lines of code).

// n_new[depth]:=n*p

-
Use more comments to describe what you are doing. Since you are making more calls to an external library, this means that you will need more comments to explain why you are doing things the way you are, and how you accomplish that. You may also need to include comments on what the external functions purpose is.

StackExchange Code Review Q#16451, answer score: 12