Talk:Deceptive numbers: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
| (4 intermediate revisions by 2 users not shown) | |||
Line 1:
Since the repunit ends in 1 5 can not be a factor of n--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 11:44, 12 February 2022 (UTC)
Since the repunit is odd, 2 cannot be a factor of '''n'''. And because the digit sum of the repunit is
All non-primes below 7<sup>2</sup> are divisible by 2, 3, or 5. So it is sufficient to start the search at 49. --[[User:Querfeld|Querfeld]] ([[User talk:Querfeld|talk]]) 14:01, 24 September 2023 (UTC)
Regarding the repunit '''R<sub>n-1</sub>''', the equation '''R<sub>n-1</sub> * 9 = 10<sup>n-1</sup> - 1''' is fulfilled. And if it is ensured, that '''n''' is not divisible by 3, then if '''R<sub>n-1</sub> * 9''' is divisible by '''n''', also '''R<sub>n-1</sub>''' is divisible by '''n'''. In that case, the check of '''R<sub>n-1</sub> mod n = 0''' can be simplified to '''10<sup>n-1</sup> mod n = 1''', which can be calculated via modular exponentiation, so that big integers are not required for this task. --[[User:Querfeld|Querfeld]] ([[User talk:Querfeld|talk]]) 19:09, 26 September 2023 (UTC)
: Yep, that certainly works! (actually nine entries were already doing just that last year) --[[User:Petelomax|Petelomax]] ([[User talk:Petelomax|talk]]) 23:52, 26 September 2023 (UTC)
:: Indeed (actually, the OCaml, Python, and C implementations have been written by me; translations followed), I just wanted to explain, how this works — to encourage implementations in languages, that don't provide native BigInt support (32-bit precision is sufficient for the first 50 ''deceptive numbers''). And the principle has already been shown on the [https://oeis.org/A000864 OEIS page] (just that they ''mod'' by '''n * 9''', instead of ruling out factor 3 in advance). But it is often faster to do the Fermat primality test ''before'' the full primality check. --[[User:Querfeld|Querfeld]] ([[User talk:Querfeld|talk]]) 10:59, 27 September 2023 (UTC)
With the [[wp:Fermat primality test]] being '''a<sup>n-1</sup> mod n = 1''', where '''[[gcd]](a, n) = 1''', it becomes obvious, that the ''deceptive numbers'' are a subset of the [[Fermat pseudoprimes]] to base '''a = 10''', with the multiples of 3 filtered out ('''10<sup>x</sup>''' already rules out the multiples of 2 and 5). --[[User:Querfeld|Querfeld]] ([[User talk:Querfeld|talk]]) 19:09, 26 September 2023 (UTC)
| |||