Prime Digit Sums


Problem Statement :


Chloe is fascinated by prime numbers. She came across the number 283002 on a sign and, though the number is not prime, found some primes hiding in it by using the following rules:

Every three consecutive digits sum to a prime:
   283002 283002 283002 283002
Every four consecutive digits sum to a prime:
   283002 283002 283002
Every five consecutive digits sum to a prime:
   283002 283002
You must answer q queries, where each query consists of an integer, n. For each n, find and print the number of positive n-digit numbers, modulo 10^9 + 7, that satisfy all three of Chloe's rules (i.e., every three, four, and five consecutive digits sum to a prime).

Input Format

The first line contains an integer, q, denoting the number of queries.
Each of the q subsequent lines contains an integer denoting the value of n for a query.

Constraints

1 <= q <= 2 * 10^4
1 <= n <= 4 * 10^5

Output Format

For each query, print the number of n-digit numbers satisfying Chloe's rules, modulo 10^9 +7, on a new line.


Solution :



title-img


                            Solution in C :

In C++ :





#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;
#define mod 1000000007;
typedef long long ll;
int func(int n){
    int sum=0;
    while(n){
        sum+=n%10;
        n/=10;
    }
    return sum;
}

int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43};
int main(){
    bool num3[1000],num4[10000];
    int num5[100000];
    for(int i=0;i<1000;i++){
        num3[i]=false;
    }
    for(int i=0;i<10000;i++){
        num4[i]=false;
    }
    for(int i=0;i<100000;i++){
        num5[i]=-1;
    }
    int a=0,b=0,d=0;
    int count1=0;
    for(int i=0;i<1000;i++){
        for(int j=0;j<14;j++){
            if(func(i)==p[j]){
                num3[i]=true;
                //cout<<i<<endl;
                count1++;
                if(i>=100)
                    a++;
            }
        }
    }
    ////cout<<" count of 3 "<<count1<<endl;
    int count2=0;
    for(int i=0;i<10000;i++){
        if(num3[i%1000]&&num3[i/10]){
            for(int j=0;j<14;j++){
                if(func(i)==p[j]){
                    num4[i]=true;
                    //cout<<i<<endl;
                    count2++;
                    if(i>=1000)
                        b++;
                }
            }
        }
    }
    //cout<<"Count of 4 "<<count2<<endl;
    int count=0;
    vector<int> num;
    for(int i=0;i<100000;i++){
        if(num4[i%10000]&&num4[i/10]){
            for(int j=0;j<14;j++){
                if(func(i)==p[j]){
                    num5[i]=count;
                    //cout<<i<<endl;
                    count++;
                    num.push_back(i);
                    if(i>=10000)
                        d++;
                }
            }
        }
    }
    //cout<<"count of 5 "<<count<<endl;
    // cout<<count<<endl;
    vector<int> gr[count];
    int count3=0;
    for(int i=0;i<count;i++){
        int temp=num[i];
        temp/=10;
        for(int j=0;j<count;j++){
            if(temp==num[j]%10000){
                gr[i].push_back(j);
                //cout<<i<<" "<<j<<" "<<num[i]<< " "<<num[j]<<endl;
                count3++;
            }
        }
    }
    //cout<<count3<<endl;
    ll dp[2][count];
    for(int i=0;i<count;i++){
        
        dp[0][i]=1;
        if(num[i]<10000){
            dp[0][i]=0;
        }
    }
    ll res[400007];
    res[1]=9;
    res[2]=90;
    res[3]=a;
    res[4]=b;
    res[5]=d;
    int r=1,c=0;

    for(int i=6;i<400001;i++){
        res[i]=0;
        for(int j=0;j<count;j++){
            dp[r][j]=0;
            for(int k=0;k<gr[j].size();k++){
                dp[r][j]+=dp[c][gr[j][k]];
                
            }
            dp[r][j]%=mod;
            res[i]+=dp[r][j];
        }
        res[i]%=mod;
        r=1-r;
        c=1-c;
    }
    int q;
    scanf("%d",&q);
    for(int a0 = 0; a0 < q; a0++){
        int n;
        scanf("%d",&n);
        cout<<res[n]<<endl;
        
        //cout<<count<<endl;
        
    }
    return 0;
}








In Java :





import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    public static boolean isPrime[] = new boolean[46];

	public static int results[] = new int[400001];

	public static boolean isGood(int n, int val) {
		int max = Math.min(n, 5);
		int mod = 100;
		for (int i = 3; i <= max; i++) {
			mod *= 10;
			int d = val;
			for (int j = 0; j < (max - i + 1); j++) {
				int d2 = d % mod;
				int sum = 0;
				while (d2 > 0) {
					sum += d2 % 10;
					d2 /= 10;
				}
				if (!isPrime[sum]) {
					return false;
				}
				d = d / 10;
			}
		}
		return true;
	}
	
	public static void initSimple() {
		for(int i=100; i<1000; i++) {
			if(isGood(3,i)) {
				results[3]++;
			}
		}
		
		for(int i=1000; i<10000; i++) {
			if(isGood(4,i)) {
				results[4]++;
			}
		}
		results[1]=9;
        results[2]=90;
	}

	public static void init() {

		Arrays.fill(isPrime, 0, isPrime.length, true);
		isPrime[0] = false;
		isPrime[1] = false;
		for (int i = 2; i < 45; i++) {
			if (isPrime[i]) {
				for (int j = 2; j < i; j++) {
					if (i % j == 0) {
						isPrime[i] = false;
					}
				}
			}
		}

		ArrayList<Integer> good = new ArrayList<Integer>();
		for (int i = 0; i < 100000; i++) {
			if (isGood(5, i)) {
				good.add(i);
			}
		}
		List<Integer> childs[] = new List[good.size()];
		for (int i = 0; i < good.size(); i++) {
			int val = (good.get(i) % 10000) * 10;
			childs[i] = new ArrayList<Integer>();
			for (int j = 0; j < 10; j++) {
				if (good.contains(val + j)) {
					childs[i].add(good.indexOf(val + j));
				}
			}
		}

		int buf1[] = new int[good.size()];
		int buf2[] = new int[good.size()];
		int temp[];
		int count = 0;
		for (int i = 0; i < buf1.length; i++) {
			if (good.get(i) >= 10000) {
				buf1[i] = 1;
				count++;
			}
		}
		results[5] = count;
		int idx = 0;
		for (int i = 6; i < results.length; i++) {
			Arrays.fill(buf2, 0, buf2.length, 0);
			count = 0;

			for (int j = 0; j < buf1.length; j++) {
				if (buf1[j] > 0) {
					List<Integer> next = childs[j];
					for (int k = 0; k < next.size(); k++) {
						idx = next.get(k);
						buf2[idx] += buf1[j];
						buf2[idx] %= 1000000007;
						count += buf1[j];
						count %= 1000000007;
					}
				}
			}
			results[i]=count;
			temp=buf1;
			buf1=buf2;
			buf2=temp;		

		}
	}

    public static void main(String[] args) {
        init();
		initSimple();
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){
            int n = in.nextInt();
            System.out.println(results[n]);
        }
    }
}








In C :





#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long long ull;
typedef unsigned int ui;

#define swap_(x, y)                                                            
  {                                                                            
    ui *z = x;                                                                 
    x = y;                                                                     
    y = z;                                                                     
  }

#define ac 20
#define ec (18 * 18)
#define mod 1000000007

#define brutec 13
ui brutes[] = {0,   9,   90,  303, 280, 218, 95,
               101, 295, 513, 737, 668, 578}; // see haskell file

ui as[ec * ac];
ui startv[] = {17, 6, 6, 2, 0, 0, 9, 3, 9, 3, 0, 0, 6, 4, 13, 15, 13, 15};
ui endv[] = {5, 11, 11, 26, 20, 20, 7, 7, 7, 5, 24, 24, 5, 5, 2, 2, 2, 1};

// 18x18 times 18x18
void multmm(ui *a, ui *b, ui *c) {
  for (int i = 0; i < 18; ++i) {
    for (int j = 0; j < 18; ++j) {
      ull x = 0;
      for (int k = 0; k < 18; ++k) {
        x += (ull)a[i * 18 + k] * (ull)b[k * 18 + j];
      }
      c[i * 18 + j] = (ui)(x % mod);
    }
  }
}

// 18x18 times 18x1
void multmv(ui *a, ui *b, ui *c) {
  for (int i = 0; i < 18; ++i) {
    ull x = 0;
    for (int k = 0; k < 18; ++k) {
      x += (ull)a[i * 18 + k] * (ull)b[k];
    }
    c[i] = (ui)(x % mod);
  }
}

// 1x18 times 18x1
ui inprod(ui *a, ui *b) {
  ull x = 0;
  for (int k = 0; k < 18; ++k) {
    x += (ull)a[k] * (ull)b[k];
  }
  return (ui)(x % mod);
}

void copy(ui *a, ui *b, int n) {
  for (int i = 0; i < n; ++i) {
    a[i] = b[i];
  }
}

void ini() {
  ui _a[] = {
      0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
      1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
  ui _b[ec];
  ui *a = _a, *b = _b;
  for (int i = 0; i < ac; ++i) {
    copy(&as[i * ec], a, ec);
    multmm(a, a, b);
    swap_(a, b);
  }
}

ui solve(int n) {
  if (n < brutec) {
    return brutes[n];
  }
  n -= 12;
  ui _v[18], _u[18];
  ui *v = _v, *u = _u;
  copy(v, startv, 18);
  ui *a = as;
  while (n) {
    if (n % 2) {
      multmv(a, v, u);
      swap_(v, u);
    }
    n /= 2;
    a += ec;
  }
  return inprod(v, endv);
}

int main() {
  ini();
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    int n;
    scanf("%d", &n);
    ui x = solve(n);
    printf("%u\n", x);
  }
  return 0;
}








In Python3 :





mod = 10**9 + 7
A = [0,0,0,0,0,2,3,15,2,0]
B = [0,0,0,0,0,4,9,13,17,2]
results = [1,9,90,303,280,218,95,101,295]
for _ in range(int(input())):
   n = int(input())
   for i in range(len(A),n):
      A.append((2*(A[i-5] + B[i-5])) % mod)
      B.append((A[i-1] + A[i-5] + 2*B[i-5]) % mod)
   print(results[n] if n < 9 else
      (5*A[n-1] + 9*A[n-2] + 19*A[n-3] + 6*A[n-4] + 3*A[n-5]
      + 2*B[n-1] + 5*B[n-2] + 20*B[n-3] + 5*B[n-4] + 4*B[n-5]) % mod)
                        




View More Similar Problems

Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →

Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →