Talk:Primes whose sum of digits is 25

The limit of primes that do not contain zeroes

For what n? (0 < n < ?) --CalmoSoft (talk) 06:27, 21 March 2021 (UTC)

I think it is possible to put an upper limit on primes whose digits sum to 25 and have no zeroes in them. The largest number with no internal zeros and a digit sum of 25 would be 1111111111111111111111111 (25 digits). --Tigerofdarkness (talk) 10:54, 21 March 2021 (UTC)

Correct, stretch goal updated. If zeroes were allowed there would be an infinite number of them. It will need reasonably decent bignum handling and a fast prime number checker. I expect this is not really do-able in asm, etc. I would put a reasonable (soft) upper limit of say 30 mins runtime on this and not be too critical of anything around that, certainly not if it actually manages to get all the way to 1.5e6 in that timeframe, and I'll be proper impressed if anyone ever manages a sub-10s, on any box in any lang. The Phix algorithm generates 1.65e7 potential candidates (without testing for primality that takes just 7.7s) as opposed (it is rather daft to test even numbers for primality!) to +2 generating 5.55e24 candidates which at that same (test-less) rate would take around 8 billion years. --Pete Lomax (talk) 12:34, 21 March 2021 (UTC)

I'll be proper impressed if anyone ever manages a sub-10s is reached.Generating the numbers for sum of digits = 25 is < 0.5 s.But on Win64 my old gmp.dll is very slow -> 7s => 15s Horsth 13:06, 29 March 2021 (UTC)

On my machine, the C++ entry compiled with g++ is coming in at 9.17 seconds so also (just) qualifies for 'proper impression' :) --PureFox (talk) 13:35, 29 March 2021 (UTC)

I am indeed proper impressed and I take my hat off to you, good sir. I've also spotted the Pascal entry does it in 6s! --Pete Lomax (talk) 17:35, 29 March 2021 (UTC)

Incidentally, the C++ version was written by Simonjsaunders using a similar approach to Phix and Go. No surprise that it's a lot faster than Go which is handicapped by the overhead of Cgo when using the GMP wrapper but is still significantly faster than Go's native big.Int. --PureFox (talk) 18:31, 29 March 2021 (UTC)

Have just played with the Pascal entry on tio, and found the answer to I don't know why there is one more probably prime: 1 and 2 fail but mpz_probab_prime_p(z,3) gets the right answer. C++ might benefit from 25->3 too. Left it to you lot to update your own entries & times. --Pete Lomax (talk) 17:58, 29 March 2021 (UTC)

Using a certainty level of 3, both the Go and C++ examples still give the same answer (1,525,141 primes) though, surprisingly, the difference in timings was negligible. --PureFox (talk) 18:49, 29 March 2021 (UTC)

Perhaps the syntax of the task title could be normalized ?

For example, something like "Primes with decimal digits summing to 25" ? Hout (talk) 11:18, 29 March 2021 (UTC)

Or just "Sum25 primes"? --Pete Lomax (talk) 12:25, 29 March 2021 (UTC)