In this post, we will solve HackerRank Prime Digit Sums Problem Solution. 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:
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 power 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
Sample Input 0
1 6
Sample Output 0
95
Prime Digit Sums C Solution
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <assert.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;
}Prime Digit Sums C++ Solution
#ifdef NOT_DMOJ
//secret header that provides answers to all questions
#include"contest includes.h"
#else
//include everything header for GCC
#include<bits/stdc++.h>
#endif
#pragma region template code
using namespace std;
template<typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxheap = priority_queue<T>;
template<typename T>
using dpair = pair<T, T>;
typedef long long ll;
typedef dpair<int> pii;
typedef dpair<long long> pll;
typedef dpair<float> pff;
typedef dpair<double> pdd;
template<class T1, class T2>
istream& operator >> (istream &is, pair<T1, T2> &p) {
return is >> p.first >> p.second;
}
template<class T1, class T2>
void operator+=(vector<T1> &v, const T2 &obj) {
v.push_back(obj);
}
template<class T1>
void operator+=(vector<T1> &v, const T1 &obj) {
v.push_back(obj);
}
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;
class range {
public:
range(int end) :_start(0), _end(end), _step(1) {}
range(int start, int end) :_start(start), _end(end), _step(1) {}
range(int start, int end, int step) :_start(start), _end(end), _step(step) {}
class iterator {
public:
iterator(int v, int s) :val(v), step(s) {};
int operator*() const {
return val;
}
int operator++() {
return (val += step);
}
bool operator==(const range::iterator &iter) const {
return val == iter.val && step == iter.step;
}
bool operator!=(const range::iterator &iter) const {
return !(this->operator==(iter));
}
private:
int val;
int step;
};
range::iterator begin() {
return{ _start, _step };
}
range::iterator end() {
return{ _end, _step };
}
private:
int _start, _end, _step;
};
#pragma endregion
const int MAXN = 4e5 + 2;
bitset<MAXN> sieve;
ll dp[2][MAXN];
bool valid(string str) {
for (int a = 0; a + 3 <= str.size(); a++) {
int sum = 0;
for (int b = 0; b < 3; b++) {
sum += str[a+b] - '0';
}
if (sieve[sum]) {
return false;
}
}
for (int a = 0; a + 4 <= str.size(); a++) {
int sum = 0;
for (int b = 0; b < 4; b++) {
sum += str[a+b] - '0';
}
if (sieve[sum]) {
return false;
}
}
for (int a = 0; a + 5 <= str.size(); a++) {
int sum = 0;
for (int b = 0; b < 5; b++) {
sum += str[a+b] - '0';
}
if (sieve[sum]) {
return false;
}
}
return true;
}
int ans[MAXN];
vector<int> children[MAXN];
vector<int> valid_nums;
int main() {
#ifdef NOT_DMOJ
freopen("text.txt", "r", stdin);
#else
cin.tie(0);
cin.sync_with_stdio(0);
#endif
sieve[0] = true;
sieve[1] = true;
for (int a = 2; a < MAXN; a++) {
if (!sieve[a]) {
for (int b = 2 * a; b < MAXN; b += a) {
sieve[b] = true;
}
}
}
for (int a = 1; a < 10000; a++) {
string st = to_string(a);
while (st.size() < 4) {
st = '0' + st;
}
if (valid(st)) {
valid_nums.push_back(a);
for (int b = 0; b < 10; b++) {
int val = a * 10 + b;
string str = to_string(val);
while (str.size() < 5) {
str = '0' + str;
}
if (valid(str)) {
children[a].push_back(val % 10000);
//cout << a << " goes to " << val << "\n";
}
}
}
}
for (int i : valid_nums) {
if (i >= 1000){
dp[0][i] = 1;
}
}
int cur = 1;
for (int a = 5; a < MAXN; a++, cur ^= 1) {
ll tmp = 0;
for (int i : valid_nums) {
dp[cur][i] = 0;
}
for (int i : valid_nums) {
for (int j : children[i]) {
dp[cur][j] += dp[!cur][i];
dp[cur][j] %= mod;
tmp += dp[!cur][i];
}
}
tmp %= mod;
ans[a] = tmp;
}
/*
int myans = 0;
for (int a = 1000; a < 10000; a++) {
if (valid(to_string(a))) {
myans++;
}
}
cout << "!" << myans << "!\n";*/
int Q;
cin >> Q;
while (Q--) {
int x;
cin >> x;
if (x == 1) {
cout << "9\n";
} else if (x == 2) {
cout << "90\n";
} else if (x == 3) {
cout << "303\n";
} else if (x == 4) {
cout << "280\n";
} else {
cout << ans[x] << "\n";
}
}
}Prime Digit Sums C Sharp Solution
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;
class Result
{
/*
* Complete the 'primeDigitSums' function below.
*
* The function is expected to return an INTEGER.
* The function accepts INTEGER n as parameter.
*/
public static int[] res = doIt();
public static int primeDigitSums(int n)
{
return res[n];
}
public static int[] doIt()
{
res =new int[400001];
long mod = 1000000007;
long[][] ar = new long[2][];
ar[0]= new long[12] { 348, 260, 248, 134, 44, 464, 242, 80, 36, 300, 114, 92 };
ar[1] = new long[12];
res[1] = 9; res[2] = 90; res[3] = 303; res[4] = 280; res[5] = 218; res[6] = 95; res[7] = 101;
res[8] = 295; res[9] = 513; res[10]= 737; res[11] = 668; res[12] = 578; res[13] = 1303; res[14] = 2449;
res[15] = 3655; res[16] = 3965;res[17] = 3446;res[18] = 5778;res[19] = 11376;
long x=1 ,y=0, mn;
for (int i = 20; i < 400001; i++)
{
x ^= 1;
y ^= 1;
ar[y][0] = (ar[x][7] + ar[x][8] + ar[x][11]) % mod;
ar[y][1] = ar[x][11];
ar[y][2] = (ar[x][9]+ar[x][6]) % mod;
ar[y][3] = ar[x][9];
ar[y][4] = ar[x][10] ;
ar[y][5] = ar[x][0];
ar[y][6] = ar[x][1];
ar[y][7] = ar[x][2];
ar[y][8] = ar[x][3];
ar[y][9] = ar[x][5];
ar[y][10] = ar[x][6];
ar[y][11] = (ar[x][7] *2) % mod;
mn = (ar[y][0]+(ar[y][1]*4) % mod+(ar[y][2]*11) % mod+(ar[y][3]*9) % mod+(ar[y][4]*2) % mod+(ar[y][5]*2) % mod+(ar[y][6]*9) % mod+(ar[y][7]*4) % mod+ar[y][8]+(ar[y][9]*5) % mod+(ar[y][10]*8) % mod+ar[y][11]) % mod;
res[i] = (int)mn;
}
return res;
}
}
class Solution
{
public static void Main(string[] args)
{
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
int q = Convert.ToInt32(Console.ReadLine().Trim());
for (int qItr = 0; qItr < q; qItr++)
{
int n = Convert.ToInt32(Console.ReadLine().Trim());
int result = Result.primeDigitSums(n);
textWriter.WriteLine(result);
}
textWriter.Flush();
textWriter.Close();
}
}Prime Digit Sums Java Solution
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
public class Solution {
static boolean[] P = new boolean[62];
static final long MOD = (long) Math.pow(10, 9) + 7l;
static Map<Integer, ThreeDigit> DIGITMAP = new HashMap<Integer, ThreeDigit>();
static Map<Long, Long> tab = new HashMap<Long, Long>();
static long[] depNUM = new long[400001];
static int NL = 400005;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
P[2] = true;
P[3] = true;
List<Integer> list = new ArrayList<Integer>();
list.add(2);
list.add(3);
for (int i = 5; i < 50; i += 6) {
int i1 = i;
int i2 = i + 2;
boolean bi1 = true;
boolean bi2 = true;
int se = (int) Math.sqrt(i2);
for (int p : list) {
if (i1 % p == 0)
bi1 = false;
if (i2 % p == 0)
bi2 = false;
if (p > se) {
break;
}
if (!bi1 && !bi2)
break;
}
if (bi1) {
P[i1] = true;
list.add(i1);
}
if (bi2) {
P[i2] = true;
list.add(i2);
}
}
for (int i = 2; i < 1000; i++) {
int temp = i / 100 + i / 10 % 10 + i % 10;
if (P[temp]) {
DIGITMAP.put(i, new ThreeDigit(i));
}
}
for (ThreeDigit td : DIGITMAP.values()) {
initDigit(td);
}
Map<Integer, Long> fourNums = new HashMap<Integer, Long>();
ThreeDigit[] tds = new ThreeDigit[1000];
int[] depSum = new int[NL + 1];
for (ThreeDigit td : DIGITMAP.values()) {
if (td.v > 100) {
fourNums.put(td.v, 1l);
depSum[3]++;
}
tds[td.v] = td;
}
depSum[1] = 9;
depSum[2] = 90;
for (int i = 4; i <= NL; i++) {
Map<Integer, Long> fourNums2 = new HashMap<Integer, Long>();
travel(fourNums, fourNums2, tds, depSum, i);
fourNums = fourNums2;
}
while (N-- > 0) {
System.out.println(depSum[sc.nextInt()]);
}
sc.close();
}
public static void travel(Map<Integer, Long> fourNums, Map<Integer, Long> fourNums2, ThreeDigit[] tds, int[] depSum,
int dep) {
for (Entry<Integer, Long> entry : fourNums.entrySet()) {
int fourNum = entry.getKey();
long num = entry.getValue();
int first = fourNum / 1000;
ThreeDigit td = tds[fourNum % 1000];
for (ThreeDigit ttd : td.set) {
if (P[first + td.threeSum + ttd.last]) {
depSum[dep] += num;
depSum[dep] %= MOD;
Long v = fourNums2.get(td.v * 10 + ttd.last);
if (v == null)
fourNums2.put(td.v * 10 + ttd.last, num);
else
fourNums2.put(td.v * 10 + ttd.last, (v + num) % MOD);
}
}
}
}
public static void initDigit(ThreeDigit td) {
for (int i = 0; i < 10; i++) {
if (P[td.threeSum + i] && P[td.twoSum + i]) {
ThreeDigit gettd = DIGITMAP.get(td.v % 100 * 10 + i);
if (!td.set.contains(gettd)) {
td.set.add(gettd);
}
}
}
}
public static class ThreeDigit {
private int v;
private int threeSum;
private int twoSum;
private int first;
private int last;
private Set<ThreeDigit> set = new HashSet<ThreeDigit>();
public void addNextDigit() {
}
public ThreeDigit(int v) {
this.v = v;
this.last = v % 10;
this.twoSum = this.last + v / 10 % 10;
this.threeSum = this.twoSum + v / 100;
this.first = this.v / 100;
}
public int hashCode() {
return this.v;
}
public boolean equals(Object o) {
ThreeDigit o1 = (ThreeDigit) o;
return this.v == o1.v;
}
}
}Prime Digit Sums JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the primeDigitSums function below.
*/
const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
const modulo = Math.pow(10,9)+7
const results = []
const aValidFiver = {
keys: [],
follower: [],
counter: []
}
let validLength = 0
const testPrime = (test) => {
return primes.includes(test.split('').reduce((sum, cur)=>sum+parseInt(cur), 0))
}
const getResult3 = () => {
let count = 0
for (let i=100;i<1000;i++) {
const strNum = i.toString()
if (testPrime(strNum)) {
count++
}
}
return count
}
const getResult4 = () => {
let count = 0
for (let i=1000;i<10000;i++) {
const strNum = i.toString()
if ( testPrime(strNum.substring(0, 3))
&& testPrime(strNum.substring(1, 4))
&& testPrime(strNum)
) {
count++
}
}
return count
}
const buildValidFiver = () => {
if (aValidFiver.keys.length === 0) {
for (let i=200;i<100000;i++) {
let test = i.toString().padStart(5,'0')
if ( testPrime(test.substring(0, 3))
&& testPrime(test.substring(1, 4))
&& testPrime(test.substring(2, 5))
&& testPrime(test.substring(0, 4))
&& testPrime(test.substring(1, 5))
&& testPrime(test)
) {
aValidFiver.keys.push(test)
aValidFiver.follower.push([])
aValidFiver.counter.push(test.startsWith('0') ? 0 : 1)
}
}
for (let i = 0; i < aValidFiver.keys.length; i++) {
const key = aValidFiver.keys[i]
for (let j = 0; j < 10; j++){
const next = (key + j).substring(1)
const indexNext = aValidFiver.keys.indexOf(next)
if (indexNext >= 0) {
aValidFiver.follower[i].push(indexNext)
}
}
}
}
validLength = aValidFiver.keys.length
}
function primeDigitSums(n) {
if (results.length === 0) {
results.push(0)
for (let i=1; i< 3; i++){
results.push(Math.pow(10,i)-Math.pow(10,i-1))
}
results.push(getResult3())
results.push(getResult4())
buildValidFiver()
results.push((aValidFiver.counter.reduce((counter, curr) => (counter+curr) % modulo, 0)) % modulo)
}
const startAddingResults = n >= results.length ? results.length : n + 1
for (let numDigits = startAddingResults; numDigits <= n; numDigits++) {
aValidFiver.lastCounter = [].concat(aValidFiver.counter)
aValidFiver.counter = new Array(validLength).fill(0)
for (let index = 0; index < aValidFiver.counter.length; index++) {
const curCount = aValidFiver.lastCounter[index]
if (curCount) {
for (let i = 0; i < aValidFiver.follower[index].length; i++) {
const next = aValidFiver.follower[index][i]
aValidFiver.counter[next] = aValidFiver.counter[next] + curCount % modulo
}
}
}
results.push((aValidFiver.counter.reduce((counter, curr) => (counter+curr) % modulo, 0)) % modulo)
}
return results[n]
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const q = parseInt(readLine(), 10);
for (let qItr = 0; qItr < q; qItr++) {
const n = parseInt(readLine(), 10);
let result = primeDigitSums(n);
ws.write(result + "\n");
}
ws.end();
}Prime Digit Sums Python Solution
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)
