Talk:Primes whose sum of digits is 25: Difference between revisions
Talk:Primes whose sum of digits is 25 (view source)
Revision as of 05:36, 24 September 2021
, 2 years agoPeak moved page Talk:Primes which sum of digits is 25 to Talk:Primes whose sum of digits is 25: acceptable English
(Created page with "== The limit of primes that do not contain zeros == <br> For what 'n'? ('''0 < n < ?'''") |
m (Peak moved page Talk:Primes which sum of digits is 25 to Talk:Primes whose sum of digits is 25: acceptable English) |
||
| (25 intermediate revisions by 7 users not shown) | |||
Line 1:
== The limit of primes that do not contain
<br> For what '''n'''? ('''0 < n < ?''') --[[User:CalmoSoft|CalmoSoft]] ([[User talk: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). --[[User:Tigerofdarkness|Tigerofdarkness]] ([[User talk: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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 12:34, 21 March 2021 (UTC)
:: <u>I'll be proper impressed if anyone ever manages a sub-10s</u> 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 [[User:Horsth|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' :) --[[User:PureFox|PureFox]] ([[User talk: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! --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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. --[[User:PureFox|PureFox]] ([[User talk: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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 18:49, 29 March 2021 (UTC)
:::testing the false checked primes.<br><Lang pascal>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;</lang>
{{out}}
<pre>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</pre>
TIO.RUN uses GMP-Version 6.1.2 too, with same results.<BR>[[User:Horsth|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 <BR>The runtime is lifted to 11.2 s :-( ;-)<BR>[[User:Horsth|Horsth]] 05:52, 31 March 2021 (UTC)
== Perhaps the syntax of the task title could be normalized ? ==
For example, something like "''Primes with decimal digits summing to 25''" ? [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 11:18, 29 March 2021 (UTC)
:Or just "Sum25 primes"? --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 12:25, 29 March 2021 (UTC)
:: Or ''Two-bit primes''? For right-ponders and elsewhere, that's slang for <big>25¢,</big> or a quarter of a (US) dollar. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 13:23, 24 April 2021 (UTC)
| |||