All about primes

Weekly challenge 158 — 28 March 2022

Week 158 - 28 Mar 2022

Task 1

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.

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

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.

#!/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); }

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

Peter Campbell Smith is hereby placed in the public domain