Talk:Primes whose sum of digits is 25
From Rosetta Code
The limit of primes that do not contain zeroes[edit]
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)
- 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)
- testing the false checked primes.
procedure OUT_FalsePrime(n:NativeINt);
Begin
writeln('false checked ',CS,' after ',n,' rounds');
end;
procedure CheckPrime;
begin
mpz_set_str(z,CS,10);
// if mpz_probab_prime_p(z,0)>0 then inc(PrimeCount);
if mpz_probab_prime_p(z,0)>0 then
if mpz_probab_prime_p(z,1)= 0 then
OUT_FalsePrime(1)
else
if mpz_probab_prime_p(z,2)= 0 then
OUT_FalsePrime(2)
else
if mpz_probab_prime_p(z,3)= 0 then
OUT_FalsePrime(3)
else
if mpz_probab_prime_p(z,5)= 0 then
OUT_FalsePrime(5)
else
inc(PrimeCount)
end;
- testing the false checked primes.
- 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)
- Output:
GMP-Version 6.1.2 false checked 2194111141 after 1 rounds false checked 128124151 after 1 rounds false checked 1134342151 after 1 rounds false checked 11973121 after 1 rounds false checked 12941161 after 1 rounds false checked 15614161 after 1 rounds false checked 132641521 after 1 rounds false checked 26157121 after 1 rounds false checked 41581321 after 1 rounds false checked 12731461 after 1 rounds false checked 1281661 after 1 rounds false checked 4411681 after 1 rounds false checked 1432242241 after 1 rounds false checked 237224311 after 1 rounds false checked 25292131 after 1 rounds false checked 12225841 after 1 rounds false checked 31294231 after 1 rounds false checked 18342241 after 1 rounds false checked 1722913 after 1 rounds false checked 14555221 after 1 rounds false checked 34124641 after 1 rounds false checked 1943521 after 3 rounds <========== astonishing small number false checked 1235851 after 1 rounds false checked 1132657 after 1 rounds false checked 64343311 after 1 rounds false checked 1584133 after 1 rounds false checked 1357441 after 1 rounds false checked 5354611 after 1 rounds false checked 28213333 after 1 rounds false checked 4922413 after 1 rounds false checked 3255271 after 1 rounds false checked 1372453 after 1 rounds false checked 5423713 after 1 rounds false checked 3542533 after 1 rounds PrimeCount of generated numbers with digits sum of 25 are 16499120 Propably primes 1525141
TIO.RUN uses GMP-Version 6.1.2 too, with same results.
Horsth 18:31, 30 March 2021 (UTC)
- Intalled GMP 6.2.1 and now a certainty level of 0 "if mpz_probab_prime_p(z,0)>0 then .." suffices to find 1525141 Propably primes
The runtime is lifted to 11.2 s :-( ;-)
Horsth 05:52, 31 March 2021 (UTC)
- Intalled GMP 6.2.1 and now a certainty level of 0 "if mpz_probab_prime_p(z,0)>0 then .." suffices to find 1525141 Propably primes
Perhaps the syntax of the task title could be normalized ?[edit]
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)
- Or Two-bit primes? For right-ponders and elsewhere, that's slang for 25Ā¢, or a quarter of a (US) dollar. -- Gerard Schildberger (talk) 13:23, 24 April 2021 (UTC)