4 ms·

For those willing to try this over toy code, I did a (horrible, horrible, I'm terribly ashamed of it) quick Python snippet to check it out: def primer():

For those willing to try this over toy code, I did a (horrible, horrible, I'm terribly ashamed of it) quick Python snippet to check it out: def primer(): p = 3 while True: is_prime = True for x in xrange(2, p): if p % x == 0: is_prime = False break if is_prime: yield p p += 2 give_prime = primer() primes = [1, 2] # had to separate this into 2 lines because Python primes.extend([give_prime.next() for x in xrange(9998)]) # so we get 10,000 primes primes_dict = {} for i in xrange(len(primes) - 1): p0 = str(primes[i])[-1] p1 = str(primes[i + 1])[-1] key = "".join([p0, "-", p1]) try: primes_dict[key] += 1 except: primes_dict[key] = 1 # let's delete the 4 outliers from the begining del(primes_dict["1-2"]) del(primes_dict["2-3"]) del(primes_dict["3-5"]) del(primes_dict["5-7"]) So long story short, my results over 10,000 primes: In [57]: primes_dict Out[57]: {'1-1': 365, '1-3': 833, '1-7': 889, '1-9': 397, '3-1': 529, '3-3': 324, '3-7': 754, '3-9': 906, '7-1': 655, '7-3': 722, '7-7': 323, '7-9': 808, '9-1': 935, '9-3': 635, '9-7': 541, '9-9': 379} And you can clearly see that the tendency to avoid the same last digit is starting to show, thow those that end in 1 are still not showing it completely. Tried with 100,000 primes but the (horrible) algorithm kinda got stuck so I settled with 10,000 to make this a "quick test". Before you go, please believe me I'm sorry for primer() and give_prime. I'll try to never do those kind of things again. Edit: I've edited this like 5 times already over little typos and bad transcription mistakes I did all over the place. Should work now.

curveship 11y ago
Shouldn't that be `if p % x == 0:`, not `if p % 2 == 0:`?
- dr_zoidberg 11y ago
  Yes, exactly, another bad typo ¬¬ Thanks for pointing it out, I did this over an IPython session and copied it in a (completely unnecesary) hurry. The results are good though :) Edit: as to keep my claim that the results are good, check this sentence from the article "...Nor could it explain why, as the pair found, primes ending in 3 seem to like being followed by primes ending in 9 more than 1 or 7." -- it backs up the data I posted :)
sdenton4 11y ago
Couple useful speedups for your loop: you only need the xrange to go up to floor of sqrt(p), since any divisor would have been found already by that point. Also you can save a lot of divisions by working as a sieve with the first couple thousand primes (so check divisibility against a store list of primes, instead of all numbers, for as long as your memory allows).
theophrastus 11y ago
So among the less populated set of same final digit-ed sequential primes is the next-digit-more-significant anti-correlated (to mitigate its 'misbehavior' ;)? In a sense, how likely does this unusual homo-digitalism rise once our focus on the final digit is shifted?
cmurphycode 11y ago
without spending the time to make a better prime generator, you can get your test going much faster by only testing factors up till sqrt(p). With just that change to your program, and asking for 100k primes: {'9-1': 8829, '1-1': 4104, '9-7': 5671, '3-9': 8387, '3-7': 7419, '7-1': 6438, '1-3': 7961, '3-3': 3604, '7-9': 8022, '1-7': 8297, '7-3': 6928, '1-9': 4605, '3-1': 5596, '7-7': 3627, '9-3': 6513, '9-9': 3994}
- dr_zoidberg 11y ago
  Thanks for the pointer, sounds like a reasonable speedup to the basic algorithm :)
chucksmash 11y ago
In the spirit of "every programmer loves to fizzbuzz", I rewrote this in Rust. Aside from rewriting it in a different language, the biggest change I made was only doing trial division against known primes <= the square root of a number we are checking for primality. Able to get the first 1,000,000 primes in 20 seconds: use std::collections::HashMap; pub fn first_n_primes(n: u64) -> Vec<u64> { let mut primes = Vec::new(); let mut candidate = 3; let mut count = 0; if n >= 1 { primes.push(2); count += 1; } while count <= n { let candidate_sqrt = ((candidate as f64).sqrt().ceil() + 1.0) as u64; let mut is_prime: bool = true; for prime in &primes { if candidate % prime == 0 { is_prime = false; break; } if prime > &candidate_sqrt { break; } } if is_prime { primes.push(candidate); count += 1; } candidate += 2; } primes } fn main() { let mut last_digit_pair_counts: HashMap<String, u64> = HashMap::new(); let primes = first_n_primes(1000000); for i in 0..(primes.len() - 1) { let last_digit0 = primes[i] % 10; let last_digit1 = primes[i+1] % 10; let digit_str = format!("{}-{}", last_digit0, last_digit1).to_string(); let counter = last_digit_pair_counts.entry(digit_str).or_insert(0); *counter += 1; } last_digit_pair_counts.remove("2-3"); last_digit_pair_counts.remove("3-5"); last_digit_pair_counts.remove("5-7"); let mut ordered_keys: Vec<String> = last_digit_pair_counts.keys().cloned().collect(); ordered_keys.sort(); for key in &ordered_keys { println!("{}: {}", key, last_digit_pair_counts[key]); } } which outputs: 1-1: 42853 1-3: 77475 1-7: 79453 1-9: 50153 3-1: 58255 3-3: 39668 3-7: 72828 3-9: 79358 7-1: 64230 7-3: 68595 7-7: 39603 7-9: 77586 9-1: 84596 9-3: 64371 9-7: 58130 9-9: 42843
- steveklabnik 11y ago
  Small speed note: Rust 1.7 just made custom hashing functions available. Rust uses a cryptographically secure hashing function by default, but for work like this, that's inappropriate. To use FNV instead: 1. add fnv to your Cargo.toml's dependencies section 2. The first few lines become: extern crate fnv; use std::collections::HashMap; use std::hash::BuildHasherDefault; use fnv::FnvHasher; type MyHasher = BuildHasherDefault<FnvHasher>; 2. and the hash creation line becomes let mut last_digit_pair_counts: HashMap<String, u64, MyHasher> = HashMap::default(); This is 17% faster on my two runs of your code. :) Other notes: format!("{}-{}", last_digit0, last_digit1).to_string(); The .to_string() is redundant here, format! already gives you a String. That should remove a bunch of allocations.
colomon 11y ago
Perl 6 version: my $primes := (1..*).grep(*.is-prime); my %count; for ^100000 -> $i { %count{($primes[$i] % 10) ~ '-' ~ ($primes[$i+1] % 10)}++; } for %count.keys.sort -> $key { say "$key = { %count{$key} }"; } (I didn't skip the outliers, but I did explicitly write out the count so that it was in order.) Results from the first 100,000 primes: 1-1 = 4104 1-3 = 7961 1-7 = 8297 1-9 = 4605 2-3 = 1 3-1 = 5596 3-3 = 3604 3-5 = 1 3-7 = 7419 3-9 = 8387 5-7 = 1 7-1 = 6438 7-3 = 6928 7-7 = 3627 7-9 = 8022 9-1 = 8830 9-3 = 6513 9-7 = 5671 9-9 = 3995
- colomon 11y ago
  And because I couldn't resist, here's a one-liner (for calculations, anyway) version: my %count := (1..*).grep(*.is-prime).map(* % 10).rotor(2 => -1).map(~*)[^100000].Bag; I think it's a bit slower than my previous version. (And much slower than the Rust version posted elsewhere here!)
21 11y ago
Using sqrt and Numba - decorating the primer function with @numba.jit(nopython=True) - allows you to check the first million in around 15 seconds.

curveship 11y ago

Shouldn't that be `if p % x == 0:`, not `if p % 2 == 0:`?

dr_zoidberg 11y ago
Yes, exactly, another bad typo ¬¬ Thanks for pointing it out, I did this over an IPython session and copied it in a (completely unnecesary) hurry. The results are good though :) Edit: as to keep my claim that the results are good, check this sentence from the article "...Nor could it explain why, as the pair found, primes ending in 3 seem to like being followed by primes ending in 9 more than 1 or 7." -- it backs up the data I posted :)

sdenton4 11y ago

Couple useful speedups for your loop: you only need the xrange to go up to floor of sqrt(p), since any divisor would have been found already by that point. Also you can save a lot of divisions by working as a sieve with the first couple thousand primes (so check divisibility against a store list of primes, instead of all numbers, for as long as your memory allows).

theophrastus 11y ago

So among the less populated set of same final digit-ed sequential primes is the next-digit-more-significant anti-correlated (to mitigate its 'misbehavior' ;)? In a sense, how likely does this unusual homo-digitalism rise once our focus on the final digit is shifted?

cmurphycode 11y ago

without spending the time to make a better prime generator, you can get your test going much faster by only testing factors up till sqrt(p). With just that change to your program, and asking for 100k primes: {'9-1': 8829, '1-1': 4104, '9-7': 5671, '3-9': 8387, '3-7': 7419, '7-1': 6438, '1-3': 7961, '3-3': 3604, '7-9': 8022, '1-7': 8297, '7-3': 6928, '1-9': 4605, '3-1': 5596, '7-7': 3627, '9-3': 6513, '9-9': 3994}

dr_zoidberg 11y ago
Thanks for the pointer, sounds like a reasonable speedup to the basic algorithm :)

chucksmash 11y ago

In the spirit of "every programmer loves to fizzbuzz", I rewrote this in Rust. Aside from rewriting it in a different language, the biggest change I made was only doing trial division against known primes <= the square root of a number we are checking for primality. Able to get the first 1,000,000 primes in 20 seconds: use std::collections::HashMap; pub fn first_n_primes(n: u64) -> Vec<u64> { let mut primes = Vec::new(); let mut candidate = 3; let mut count = 0; if n >= 1 { primes.push(2); count += 1; } while count <= n { let candidate_sqrt = ((candidate as f64).sqrt().ceil() + 1.0) as u64; let mut is_prime: bool = true; for prime in &primes { if candidate % prime == 0 { is_prime = false; break; } if prime > &candidate_sqrt { break; } } if is_prime { primes.push(candidate); count += 1; } candidate += 2; } primes } fn main() { let mut last_digit_pair_counts: HashMap<String, u64> = HashMap::new(); let primes = first_n_primes(1000000); for i in 0..(primes.len() - 1) { let last_digit0 = primes[i] % 10; let last_digit1 = primes[i+1] % 10; let digit_str = format!("{}-{}", last_digit0, last_digit1).to_string(); let counter = last_digit_pair_counts.entry(digit_str).or_insert(0); *counter += 1; } last_digit_pair_counts.remove("2-3"); last_digit_pair_counts.remove("3-5"); last_digit_pair_counts.remove("5-7"); let mut ordered_keys: Vec<String> = last_digit_pair_counts.keys().cloned().collect(); ordered_keys.sort(); for key in &ordered_keys { println!("{}: {}", key, last_digit_pair_counts[key]); } } which outputs: 1-1: 42853 1-3: 77475 1-7: 79453 1-9: 50153 3-1: 58255 3-3: 39668 3-7: 72828 3-9: 79358 7-1: 64230 7-3: 68595 7-7: 39603 7-9: 77586 9-1: 84596 9-3: 64371 9-7: 58130 9-9: 42843

steveklabnik 11y ago
Small speed note: Rust 1.7 just made custom hashing functions available. Rust uses a cryptographically secure hashing function by default, but for work like this, that's inappropriate. To use FNV instead: 1. add fnv to your Cargo.toml's dependencies section 2. The first few lines become: extern crate fnv; use std::collections::HashMap; use std::hash::BuildHasherDefault; use fnv::FnvHasher; type MyHasher = BuildHasherDefault<FnvHasher>; 2. and the hash creation line becomes let mut last_digit_pair_counts: HashMap<String, u64, MyHasher> = HashMap::default(); This is 17% faster on my two runs of your code. :) Other notes: format!("{}-{}", last_digit0, last_digit1).to_string(); The .to_string() is redundant here, format! already gives you a String. That should remove a bunch of allocations.

colomon 11y ago

Perl 6 version: my $primes := (1..*).grep(*.is-prime); my %count; for ^100000 -> $i { %count{($primes[$i] % 10) ~ '-' ~ ($primes[$i+1] % 10)}++; } for %count.keys.sort -> $key { say "$key = { %count{$key} }"; } (I didn't skip the outliers, but I did explicitly write out the count so that it was in order.) Results from the first 100,000 primes: 1-1 = 4104 1-3 = 7961 1-7 = 8297 1-9 = 4605 2-3 = 1 3-1 = 5596 3-3 = 3604 3-5 = 1 3-7 = 7419 3-9 = 8387 5-7 = 1 7-1 = 6438 7-3 = 6928 7-7 = 3627 7-9 = 8022 9-1 = 8830 9-3 = 6513 9-7 = 5671 9-9 = 3995

colomon 11y ago
And because I couldn't resist, here's a one-liner (for calculations, anyway) version: my %count := (1..*).grep(*.is-prime).map(* % 10).rotor(2 => -1).map(~*)[^100000].Bag; I think it's a bit slower than my previous version. (And much slower than the Rust version posted elsewhere here!)

21 11y ago

Using sqrt and Numba - decorating the primer function with @numba.jit(nopython=True) - allows you to check the first million in around 15 seconds.