Peter
Peter Campbell Smith

All about primes

Weekly challenge 158 — 28 March 2022

Week 158 - 28 Mar 2022

Task 1

Task — Additive primes

Write a script to find out all additive primes <= 100. Additive primes are prime numbers for which the sum of their decimal digits are also primes.

Examples


Example 1:
47, as 4 + 7 = 11, which is prime.

Analysis

We are looking for prime numbers whose digits sum to a prime. Given that I've resorted to using is_prime from Math::Prime::Util, there isn't much left to do.

One could try a number of ways of summing the digits. Perhaps the neatest (version 1) is:

$sd = 0;
$sd += $1 while $n =~ m|(\d)|g;

- a single line and reasonably comprehensible, and works for a bigint.

Another thought (version 2) was:

$n =~ s|(\d)|$1+|g;
$sd = eval($n . '0');

This inserts a plus after each digit of $n, appends a zero and evals the resulting sum.

And the arithmetic way (version 3) is:

while ($n > 0) {
    $sd += $n % 10;
    $n = int($n / 10);
}

So which is the most efficient? I tested them each on a 20-digit number, running the sum a million times, and the results were:

  • Version 1 - 23 seconds
  • Version 2 - 89 seconds
  • Version 3 - 15 seconds.

So version 2 loses out, probably because the eval means invoking the compiler and probably also prevents any optimisation. But probably they would all be fine for any real-world task.

Script


#!/usr/bin/perl

# Peter Campbell Smith - 2022-03-30
# PWC 158 task 1

use v5.28;
use strict;
use warnings;
use utf8;

use Math::Prime::Util 'is_prime';

my ($j, $s);

# find additive primes
for $j (1 .. 100) {
    next unless is_prime($j);
    $s = $j % 10 + int($j / 10) % 10 + int($j / 100) % 10;
    say qq[$j is an additive prime whose digits sum to $s] if is_prime($s);
}

Output

2 is an additive prime whose digits sum to 2
3 is an additive prime whose digits sum to 3
5 is an additive prime whose digits sum to 5
7 is an additive prime whose digits sum to 7
11 is an additive prime whose digits sum to 2
23 is an additive prime whose digits sum to 5
29 is an additive prime whose digits sum to 11
41 is an additive prime whose digits sum to 5
43 is an additive prime whose digits sum to 7
47 is an additive prime whose digits sum to 11
61 is an additive prime whose digits sum to 7
67 is an additive prime whose digits sum to 13
83 is an additive prime whose digits sum to 11
89 is an additive prime whose digits sum to 17

The content of this website which has been created by
Peter Campbell Smith is hereby placed in the public domain