For those who enjoy burning cpu cycles !
m1277 = 2 ^ 1277 - 1 is not prime.
It easy to check it with the Lucas-Lehmer test.
But we don't know any of its divisors, which is quite fascinating.
Up to 100 it is relatively simple, if you remove the even numbers, the multiples of 3 (summing up their digits recursively gives 3 6 or 9), and those that end at 5, you end up with 25 numbers out of which 22 (88%) are primes. If you further exclude 49 which you should remember is 7^2 from the multiplication table, and 77 that is obviously divisible by 7, you are left with 22/23 chance a number that passes these exclusion criteria is not 91 and hence it is a prime.
The fixed point here being that if you add up a list of 1 digits, you'll always reach the same number (`sum([1]) = 1`). The best known is probably the hailstone sequence.
I wonder what the underlying human intuition is for 'prime-ness' and why it might break down with larger numbers. Odd numbers in the rightmost position? The 'shape' of the number (phonaesthesia, the bouba/kiki effect)? Maybe they just sort of feel scary?
For n < 100 to be composite you need a factor < sqrt(100) = 10. Rules for 2, 3, 5 are easy to try quickly. That leaves 7, but up to 7*9 you should remember it from multiplication tables. 77 is quite obviously divisible by 11 too, and then it's 7*13 = 91 as the last boss. But I feel that once you realize how special 91 is in that context, you won't forget it again.
The example given in the article is 2^127 - 1, which was historically proved to be prime without computers using a clever method now known as the Lucas-Lehmer test. Your algorithm is not practical for that number.
Readit News
http://calcoastrails.com/
(factorial(170,141,183,460,469,231,731,687,303,715,884,105,726) + 1)%(170,141,183,460,469,231,731,687,303,715,884,105,727) == 0
My fun fact is that this type of operation (repeatedly applying a child operation until you reach a fixed point) is called persistence.
https://en.wikipedia.org/wiki/Persistence_of_a_number
The fixed point here being that if you add up a list of 1 digits, you'll always reach the same number (`sum([1]) = 1`). The best known is probably the hailstone sequence.
https://en.wikipedia.org/wiki/Collatz_conjecture
I'm partial to multiplicative persistence.
https://www.youtube.com/watch?v=Wim9WJeDTHQ [15m]
What does this part mean? For example 57.
Deleted Comment
Deleted Comment
Dead Comment
That is it. That is all. Pish posh.
If a number is not prime, then it is the product of at least two numbers smaller than itself.
If any of them are larger than its square root, all others must be smaller, or their product would be larger than the candidate prime.
Ergo, just check that the candidate is not evenly divisible by any number equal or lower than its square root.
This reasoning holds, independent of scale.
QED. Check mate. Shazam.