Talk:Deceptive numbers: Difference between revisions
(yep) |
m (Ocaml/Mathematical were already doing that last year) |
||
| Line 5: | Line 5: | ||
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.<br> |
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.<br> |
||
: Yep, that certainly works! --[[User:Petelomax|Petelomax]] ([[User talk:Petelomax|talk]]) 23:52, 26 September 2023 (UTC) |
: Yep, that certainly works! (actually Ocaml/Mathematica were already doing just that last year) --[[User:Petelomax|Petelomax]] ([[User talk:Petelomax|talk]]) 23:52, 26 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> - 1''' already rules out the multiples of 2 and 5). --[[User:Querfeld|Querfeld]] ([[User talk:Querfeld|talk]]) 19:09, 26 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> - 1''' already rules out the multiples of 2 and 5). --[[User:Querfeld|Querfeld]] ([[User talk:Querfeld|talk]]) 19:09, 26 September 2023 (UTC) |
||
Revision as of 00:04, 27 September 2023
Since the repunit ends in 1 5 can not be a factor of n--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 n - 1, 3 cannot be a factor of n (an integer is divisible by 3, if its digit sum is divisible by 3, but n - 1 and n cannot both be divisible by 3).
All non-primes below 72 are divisible by 2, 3, or 5. So it is sufficient to start the search at 49. --Querfeld (talk) 14:01, 24 September 2023 (UTC)
Regarding the repunit Rn-1, the equation Rn-1 * 9 = 10n-1 - 1 is fulfilled. And if it is ensured, that n is not divisible by 3, then if Rn-1 * 9 is divisible by n, also Rn-1 is divisible by n. In that case, the check of Rn-1 mod n = 0 can be simplified to 10n-1 mod n = 1, which can be calculated via modular exponentiation, so that big integers are not required for this task.
- Yep, that certainly works! (actually Ocaml/Mathematica were already doing just that last year) --Petelomax (talk) 23:52, 26 September 2023 (UTC)
With the wp:Fermat primality test being an-1 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 (10x - 1 already rules out the multiples of 2 and 5). --Querfeld (talk) 19:09, 26 September 2023 (UTC)