Algorithm to find Lucky Numbers

Question

I came across this question.A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky? 1 <= A <= B <= 10¹⁸. I tried this.

• First I generated all possible primes between 1 and the number that could be resulted by summing the squares (81 *18 = 1458).
  
  
• I read in A and B find out maximum number that could be generated by summing the digits If B is a 2 digit number ( the max number is 18 generated by 99).
  
  
• For each prime number between 1 an max number. I applied integer partition algorithm.
  
  
• For each possible partition I checked whether their sum of squares of their digits form prime. If so the possible permutations of that partition are generated and if they lie with in range they are lucky numbers.
  

---

This is the implementation:

#include<stdio.h> #include<malloc.h> #include<math.h> #include <stdlib.h> #include<string.h> long long luckynumbers; int primelist[1500];  int checklucky(long long possible,long long a,long long b){     int prime =0;     while(possible>0){             prime+=pow((possible%10),(float)2);             possible/=10;     }         if(primelist[prime]) return 1;         else return 0; } long long getmax(int numdigits){         if(numdigits == 0) return 1;          long long maxnum =10;              while(numdigits>1){                         maxnum = maxnum *10;                         numdigits-=1;              }          return maxnum;   } void permuteandcheck(char *topermute,int d,long long a,long long b,int digits){     if(d == strlen(topermute)){             long long possible=atoll(topermute);             if(possible >= getmax(strlen(topermute)-1)){  // to skip the case of getting already read numbers like 21 and 021(permuted-210                  if(possible >= a && possible <= b){                      luckynumbers++;                 }             }     }     else{         char lastswap ='\0';         int i;         char temp;         for(i=d;i<strlen(topermute);i++){             if(lastswap == topermute[i])                 continue;             else                 lastswap = topermute[i];             temp = topermute[d];             topermute[d] = topermute[i];             topermute[i] = temp;              permuteandcheck(topermute,d+1,a,b,digits);              temp = topermute[d];             topermute[d] = topermute[i];             topermute[i] = temp;         }      }  }   void findlucky(long long possible,long long a,long long b,int digits){     int i =0;     if(checklucky(possible,a,b)){         char topermute[18];         sprintf(topermute,"%lld",possible);         permuteandcheck(topermute,0,a,b,digits);     } }   void  partitiongenerator(int k,int n,int numdigits,long long  possible,long long a,long long b,int digits){     if(k > n || numdigits > digits-1 || k > 9) return;     if(k == n){          possible+=(k*getmax(numdigits));          findlucky(possible,a,b,digits);         return;     }     partitiongenerator(k,n-k,numdigits+1,(possible + k*getmax(numdigits)),a,b,digits);     partitiongenerator(k+1,n,numdigits,possible,a,b,digits);  }   void calcluckynumbers(long long a,long long b){     int i;     int numdigits = 0;     long long temp = b;     while(temp > 0){         numdigits++;         temp/=10;     }      long long maxnum =getmax(numdigits)-1;     int maxprime=0,minprime =0;     temp = maxnum;     while(temp>0){         maxprime+=(temp%10);         temp/=10;     }     int start = 2;     for(;start <= maxprime ;start++){             if(primelist[start]) {                 partitiongenerator(0,start,0,0,a,b,numdigits);             }     }     }    void generateprime(){     int i = 0;     for(i=0;i<1500;i++)         primelist[i] = 1;     primelist[0] = 0;     primelist[1] = 0;     int candidate = 2;     int topCandidate = 1499;     int thisFactor = 2;     while(thisFactor * thisFactor <= topCandidate){         int  mark = thisFactor + thisFactor;         while(mark <= topCandidate){             *(primelist + mark) = 0;             mark += thisFactor;         }         thisFactor++;         while(thisFactor <= topCandidate && *(primelist+thisFactor) == 0) thisFactor++;     }  } int main(){         char input[100];         int cases=0,casedone=0;     long long a,b;     generateprime();         fscanf(stdin,"%d",&cases);         while(casedone < cases){         luckynumbers = 0;                 fscanf(stdin,"%lld %lld",&a,&b);         int i =0;                calcluckynumbers(a,b);                 casedone++;         }  } 

---

The algorithm is too slow. I think the answer can be found based on the property of numbers.Kindly share your thoughts. Thank you.

Answer 1

Excellent solution OleGG, But your code is not optimized. I have made following changes to your code,

1. It does not require to go through 9*9*i for k in count_lucky function, because for 10000 cases it would run that many times, instead i have reduced this value through start and end.

2. i have used ans array to store intermediate results. It might not look like much but over 10000 cases this is the major factor that reduces the time.

I have tested this code and it passed all the test cases. Here is the modified code:

    #include <stdio.h>      const int MAX_LENGTH = 18;     const int MAX_SUM = 162;     const int MAX_SQUARE_SUM = 1458;     int primes[1460];     unsigned long long dyn_table[20][164][1460];     //changed here.......1     unsigned long long ans[19][10][164][1460];  //about 45 MB      int start[19][163];     int end[19][163];     //upto here.........1     void gen_primes() {         for (int i = 0; i <= MAX_SQUARE_SUM; ++i) {             primes[i] = 1;         }         primes[0] = primes[1] = 0;          for (int i = 2; i * i <= MAX_SQUARE_SUM; ++i) {             if (!primes[i]) {                 continue;             }             for (int j = 2; i * j <= MAX_SQUARE_SUM; ++j) {                 primes[i*j] = 0;             }         }     }      void gen_table() {         for (int i = 0; i <= MAX_LENGTH; ++i) {             for (int j = 0; j <= MAX_SUM; ++j) {                 for (int k = 0; k <= MAX_SQUARE_SUM; ++k) {                     dyn_table[i][j][k] = 0;                 }             }         }         dyn_table[0][0][0] = 1;          for (int i = 0; i < MAX_LENGTH; ++i) {             for (int j = 0; j <= 9 * i; ++j) {                 for (int k = 0; k <= 9 * 9 * i; ++k) {                     for (int l = 0; l < 10; ++l) {                         dyn_table[i + 1][j + l][k + l*l] += dyn_table[i][j][k];                     }                 }             }         }     }      unsigned long long count_lucky (unsigned long long maxp) {         unsigned long long result = 0;         int len = 0;         int split_max[MAX_LENGTH];         while (maxp) {             split_max[len] = maxp % 10;             maxp /= 10;             ++len;         }         int sum = 0;         int sq_sum = 0;         unsigned long long step_result;         unsigned long long step_;         for (int i = len-1; i >= 0; --i) {             step_result = 0;             int x1 = 9*i;             for (int l = 0; l < split_max[i]; ++l) {     //changed here........2                 step_ = 0;                 if(ans[i][l][sum][sq_sum]!=0)                     {                         step_result +=ans[i][l][sum][sq_sum];                         continue;                     }                 int y = l + sum;                 int x = l*l + sq_sum;                 for (int j = 0; j <= x1; ++j) {                     if(primes[j + y])                         for (int k=start[i][j]; k<=end[i][j]; ++k) {                             if (primes[k + x]) {                                 step_result += dyn_table[i][j][k];                                 step_+=dyn_table[i][j][k];                             }                     }                  }                  ans[i][l][sum][sq_sum] = step_;     //upto here...............2             }             result += step_result;             sum += split_max[i];             sq_sum += split_max[i] * split_max[i];         }          if (primes[sum] && primes[sq_sum]) {             ++result;         }          return result;     }      int main(int argc, char** argv) {         gen_primes();         gen_table();      //changed here..........3         for(int i=0;i<=18;i++)             for(int j=0;j<=163;j++)                 {                     for(int k=0;k<=1458;k++)                             if(dyn_table[i][j][k]!=0ll)                                 {                                     start[i][j] = k;                                     break;                                                                }                      for(int k=1460;k>=0;k--)                             if(dyn_table[i][j][k]!=0ll)                                 {                                     end[i][j]=k;                                     break;                                                                }                 }     //upto here..........3         int cases = 0;         scanf("%d",&cases);         for (int i = 0; i < cases; ++i) {             unsigned long long a, b;              scanf("%lld %lld", &a, &b);     //changed here......4             if(b == 1000000000000000000ll)                 b--;     //upto here.........4             printf("%lld\n", count_lucky(b) - count_lucky(a-1));         }         return 0;  } 

Explanation:

gen_primes() and gen_table() are pretty much self explanatory.

count_lucky() works as follows:

split the number in split_max[], just storing single digit number for ones, tens, hundreds etc. positions. The idea is: suppose split_map[2] = 7, so we need to calculate result for

1 in hundreds position and all 00 to 99.

2 in hundreds position and all 00 to 99.

. .

7 in hundreds position and all 00 to 99.

this is actually done(in l loop) in terms of sum of digits and sum of square of digits which has been precalcutaled. for this example: sum will vary from 0 to 9*i & sum of square will vary from 0 to 9*9*i...this is done in j and k loops. This is repeated for all lengths in i loop

This was the idea of OleGG.

For optimization following is considered:

1. its useless to run sum of squares from 0 to 9*9*i as for particular sums of digits it would not go upto the full range. Like if i = 3 and sum equals 5 then sum of square would not vary from 0 to 9*9*3.This part is stored in start[] and end[] arrays using precomputed values.

2. value for particular number of digits and particular digit at most significant position of number and upto particular sum and upto particular sum of square isstored for memorization. Its too long but still its about 45 MB. I believe this could be further optimized.