Prime Digit Sums

Question

So I'm doing one of those programming challenges on HackerRank to help build my skills. (No this is NOT for an interview! The problem I am on is the Prime Digit Sum. (Full description: https://www.hackerrank.com/challenges/prime-digit-sums/problem) Basically given a value n, I am to find all numbers that are n digits long that meet the following three criteria:

• Every 3 consecutive digits sums to a prime number
• Every 4 consecutive digits sums to a prime number
• Every 5 consecutive digits sums to a prime number

See the link for a detailed breakdown...

I've got a basic function that works, problem is that when n gets big enough it breaks:

#!/bin/ruby
require 'prime'

def isChloePrime?(num)
    num = num.to_s
    num.chars.each_cons(5) do |set|
        return false unless Prime.prime?(set.inject(0) {|sum, i| sum + i.to_i})
    end
    num.chars.each_cons(4) do |set|
        return false unless Prime.prime?(set.inject(0) {|sum, i| sum + i.to_i})
    end
    num.chars.each_cons(3) do |set|
        return false unless Prime.prime?(set.inject(0) {|sum, i| sum + i.to_i})
    end
    return true
end

def primeDigitSums(n)
    total = 0
    (10**(n-1)..(10**n-1)).each do |i| 
       total += 1 if isChloePrime?(i)
    end
    return total
end

puts primeDigitSums(6) # prints 95 as expected
puts primeDigitSums(177779) # runtime error

If anyone could point me in the right direction that would be awesome. Not necessarily looking for a "here's the answer". Ideally would love a "try looking into using this function...".

UPDATE here is version 2:

#!/bin/ruby
require 'prime'

@primes = {}

def isChloePrime?(num)
  num = num.to_s
  (0..num.length-5).each do |i|
    return false unless @primes[num[i,5]]
  end
  return true
end

def primeDigitSums(n)
  total = 0
  (10**(n-1)...(10**n)).each do |i|
    total += 1 if isChloePrime?(i)
  end
  return total
end

(0..99999).each do |val|
    @primes[val.to_s.rjust(5, "0")] = true if [3,4,5].all? { |n| val.digits.each_cons(n).all? { |set| Prime.prime? set.sum } }
end

Answer 1

I regard every non-negative integer to be valid if the sum of every sequence of 3, 4 and 5 of its digits form a prime number.

Construct set of relevant prime numbers

We will need to determine if the sums of digits of 3-, 4- and 5-digit numbers are prime. The largest number will therefore be no larger than 5 * 9. It is convenient to construct a set of those primes (a set rather than an array to speed lookups).

require 'prime'
require 'set'

primes = Prime.each(5*9).to_set
  #=> #<Set: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43}>

Construct transition hash

valid1 is a hash whose keys are all 1-digit numbers (all of which are valid). The value of the key 0 is an array of all 1-digit numbers. For 1-9 the values are arrays of 2-digit numbers (all of which are valid) that are obtained by appending a digit to the key. Collectively, the values include all 2-digit numbers.

valid1 = (0..9).each_with_object({}) { |v1,h|
  h[v1] = 10.times.map { |i| 10 * v1 + i } }

valid2 is a hash that maps 2-digit numbers (all valid) to arrays of valid 3-digit numbers that are obtained by appending a digit to the 2-digit number. Collectively, the values include all valid 3-digit numbers. All values are non-empty arrays.

valid2 = (10..99).each_with_object({}) do |v2,h|
  p = 10 * v2
  b, a = v2.digits
  h[v2] = (0..9).each_with_object([]) { |c,arr|
    arr << (p+c) if primes.include?(a+b+c) }
end

Note that Integer#digits returns an array with the 1's digit first.

valid3 is a hash that maps valid 3-digit numbers to arrays of valid 4-digit numbers that are obtained by appending a digit to the key. Collectively, the values include all valid 4-digit numbers. 152 of the 303 values are empty arrays.

valid3 = valid2.values.flatten.each_with_object({}) do |v3,h|
  p = 10 * v3
  c, b, a = v3.digits
  h[v3] = (0..9).each_with_object([]) do |d,arr|
    t = b+c+d
    arr << (p+d) if primes.include?(t) && primes.include?(t+a)
  end
end

valid4 is a hash that maps valid 4-digit numbers to arrays of valid 4-digit numbers that are obtained by appending a digit to the key and dropping the first digit of key. valid5.values.flatten.size #=> 218 is the number of valid 5-digit numbers. 142 of the 280 values are empty arrays.

valid4 = valid3.values.flatten.each_with_object({}) do |v4,h|
  p = 10 * v4
  d, c, b, a = v4.digits
  h[v4] = (0..9).each_with_object([]) do |e,arr|
    t = c+d+e
    arr << ((p+e) % 10_000) if primes.include?(t) &&
      primes.include?(t += b) && primes.include?(t + a)
  end
end

We merge these four hashes to form a single hash @transition. The former hashes are no longer needed. @transition has 294 keys.

@transition = [valid1, valid2, valid3, valid4].reduce(:merge)
  #=> {0=>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
  #    1=>[10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
  #    ...
  #    9=>[90, 91, 92, 93, 94, 95, 96, 97, 98, 99],
  #    10=>[101, 102, 104, 106], 11=>[110, 111, 113, 115, 119], 
  #    ...
  #    97=>[971, 973, 977], 98=>[980, 982, 986], 99=>[991, 995],
  #    101=>[1011], 102=>[1020], 104=>[], 106=>[], 110=>[1101], 
  #    ...
  #    902=>[9020], 904=>[], 908=>[], 911=>[9110], 913=>[], 917=>[],
  #    1011=>[110], 1020=>[200], 1101=>[], 1110=>[], 1200=>[],
  #    ...
  #    8968=>[], 9020=>[200], 9110=>[], 9200=>[]}

Transition method

This is the method that will be used to update counts each time n, the number of digits, is incremented by one.

def next_counts(counts)
  counts.each_with_object({}) do |(k,v),new_valid|
    @transition[k].each do |new_v|
      (new_valid[new_v] = new_valid[new_v].to_i + v) if @transition.key?(k)
    end
  end
end

prime_digit_sum method

def prime_digit_sum(n)
  case n
  when 1 then 10
  when 2 then 90
  when 3 then @transition.sum { |k,v| (10..99).cover?(k) ? v.size : 0 }
  else
    counts = @transition.select { |k,_| (100..999).cover?(k) }.
                         values.flatten.product([1]).to_h   
    (n - 4).times { counts = next_counts(counts) }
    counts.values.sum % (10**9 + 7)
  end
end

Note that, for n = 4 the hash counts has keys that are valid 4-digit numbers and values that all equal 1:

counts = @transition.select { |k,_| (100..999).cover?(k) }.
  values.flatten.product([1]).to_h   
  #=> {1011=>1, 1020=>1, 1101=>1, 1110=>1, 1200=>1, 2003=>1, 2005=>1,
  #    ...
  #    8902=>1, 8920=>1, 8968=>1, 9020=>1, 9110=>1, 9200=>1}

counts.size
  #=> 280

As shown, for n >= 5, counts is updated each time n is incremented by one. The sum of the values equals the number of valid n-digit numbers.

The number formed by the last four digits of every valid n-digit numbers is one of count's keys. The value of each key is an array of numbers that comprise the last four digits of all valid (n+1)-digit numbers that are produced by appending a digit to the key.

Consider, for example, the value of counts for n = 6, which is found to be the following.

counts
  #=> {1101=>1, 2003=>4, 2005=>4, 300=>1, 302=>1, 304=>1, 308=>1, 320=>1,
  #    322=>1, 326=>1, 328=>1, 380=>1, 382=>1, 386=>1, 388=>1, 500=>1,
  #    502=>1, 506=>1, 508=>1, 560=>1, 562=>1, 566=>1, 568=>1, 1200=>7,
  #    3002=>9, 3020=>4, 3200=>6, 5002=>6, 9200=>4, 200=>9, 1020=>3, 20=>3,
  #    5200=>4, 201=>2, 203=>2, 205=>2, 209=>2, 5020=>2, 9020=>1}

Consider the key 2005 and note that

@transition[2005]
  #=> [50, 56]

We see that there are 4 valid 6-digit numbers whose last four digits are 2005 and that, for each of those 4 numbers, a valid number is produced by adding the digits 0 and 6, resulting in numbers whose last 5-digits are 20050 and 20056. However, we need only keep the last four digits, 0050 and 0056, which are the numbers 50 and 56. Therefore, when recomputing counts for n = 7--call it counts7--we add 4 to both counts7[50] and counts7[56]. Other keys k of counts (for n=6) may be such that @transition[k] have values that include 50 and 56, so they too would contribute to counts7[50] and counts7[50].

Selective results

Let's try it for various values of n

puts "digits  nbr valid*  seconds"
[1, 2, 3, 4, 5, 6, 20, 50, 100, 1_000, 10_000, 40_000].each do |n|
  print "%6d" % n
  t = Time.now
  print "%11d" % prime_digit_sum(n)
  puts "%10f" % (Time.now-t).round(4)
end
puts "\n* modulo (10^9+7)"

digits  nbr valid*  seconds
     1         10  0.000000
     2         90  0.000000
     3        303  0.000200
     4        280  0.002200
     5        218  0.000400
     6         95  0.000400
    20      18044  0.000800
    50  215420656  0.001400
   100  518502061  0.002700
  1000  853799949  0.046100
 10000  590948890  0.474200
 40000  776929051  2.531600

Answer 2

I would approach the problem by pre-calculating a list of all the allowed 5-digit sub-sequences: '00002' fails while '28300' is allowed etc. This could perhaps be set up as a binary array or hash set.

Once you have the list, then you can check any number by moving a 5-digit frame over the number one step at a time.