mersenneforum.org Sums of all Squares
 Register FAQ Search Today's Posts Mark Forums Read

 2010-04-22, 03:46 #111 CRGreathouse     Aug 2006 593810 Posts I'm looking at your posts on the other forum. You write: Code: #include #include #include #pragma precision=log10l(ULLONG_MAX)/2 typedef enum { FALSE=0, TRUE=1 } BOOL; BOOL is_prime( int p ){ if( p == 2 ) return TRUE; else if( p <= 1 || p % 2 == 0 ) return FALSE; else { BOOL prime = TRUE; const int to = sqrt(p); int i; for(i = 3; i <= to; i+=2) if (!(prime = p % i))break; return prime; } } BOOL is_mersenne_prime( int p ){ if( p == 2 ) return TRUE; else { const long long unsigned m_p = ( 1LLU << p ) - 1; long long unsigned s = 4; int i; for (i = 3; i <= p; i++){ s = (s * s - 2) % m_p; } return s == 0; } } int main(int argc, char **argv){ const int upb = log2l(ULLONG_MAX)/2; int p; printf(" Mersenne primes:\n"); for( p = 2; p <= upb; p += 1 ){ if( is_prime(p) && is_mersenne_prime(p) ){ printf (" M%u",p); } } printf("\n"); } This code looks fine for p up to 31, but it can't work any higher. It uses multiplication mod 2^p - 1, so the numbers used need to be able to fit (2^p - 2)^2 at the very least. For that section they use 64-bit unsigned integers, which are barely enough for 31. For the next Mersenne prime 2^61 - 1, you need at least 122 bits (practically, 128); for the following, at least 178 bits (practically, 192). Also, I would be wary of the call to sqrt; it may not round properly for sufficiently large numbers. Just for kicks, here's how I'd code the basic trial division prime tester: Code: int isprime(int p ) { if(!(p&1)) return p == 2; if(p%3 == 0) return p == 3; if(p < 25) return p > 1; int i, to = (int)sqrt(p + 0.5); for(i = 5; i <= to; i += 6) { if (p%i == 0) return 0; if (p%(i+2) == 0) return 0; } return 1; } Last fiddled with by CRGreathouse on 2010-04-22 at 03:51
 2010-12-12, 20:53 #112 davar55     May 2004 New York City 2·2,099 Posts Another possibly interesting variation: 2^2 + 3^3 + 5^5 + ... + p^p = 10mK What is the smallest prime p such that the sum of squares of all primes up to p is a multiple of 10 (or 100 or 1000 and so on). (I think somewhere in these series we'll get numeric pointers to empirical evidence connecting some number theoretical conjectures.)
2010-12-12, 21:19   #113
CRGreathouse

Aug 2006

2×2,969 Posts

Quote:
 Originally Posted by davar55 Another possibly interesting variation: 2^2 + 3^3 + 5^5 + ... + p^p = 10mK What is the smallest prime p such that the sum of squares of all primes up to p is a multiple of 10 (or 100 or 1000 and so on).
11, 751, 1129, then something big.

Quote:
 Originally Posted by davar55 (I think somewhere in these series we'll get numeric pointers to empirical evidence connecting some number theoretical conjectures.)
Why?

 2010-12-12, 21:22 #114 davar55     May 2004 New York City 2×2,099 Posts Something big? Now wouldn't that be cool to see ...
2010-12-12, 21:43   #115
CRGreathouse

Aug 2006

10111001100102 Posts

Quote:
 Originally Posted by davar55 Something big? Now wouldn't that be cool to see ...
Nah, it turns out it's only 361,649. My code had been storing the full numbers (which are large) and was running slowly as a result.

 2010-12-12, 21:52 #116 davar55     May 2004 New York City 419810 Posts So far, this (sum p^p) sequence is: 11 751 1129 361649 Couldn't have done that without a computer.
2010-12-13, 01:39   #117
NBtarheel_33

"Nathan"
Jul 2008
Maryland, USA

3·7·53 Posts
Methinks your calculator needs new batteries

Quote:
 Originally Posted by davar55 So far, this (sum p^p) sequence is: 11 751 1129 361649 Couldn't have done that without a computer.
2^2 = 4
2^2 + 3^3 = 4 + 27 = 31
2^2 + 3^3 + 5^5 = 4 + 27 + 3125 = 3156
2^2 + 3^3 + 5^5 + 7^7 = 826699

The next term brings the sum to 285 billion and change (i.e. 285e9), and the term after that brings the sum to over 303 trillion (i.e. 303e12).

Looking at the sum mod 10, we see that 2^2 = 4, 3^3 = 7, 5^5 = 5, 7^7 = 3, 11^11 = 1. This adds up to 0 (mod 10). Hence,

2^2 + 3^3 + 5^5 + 7^7 + 11^11 = 285,312,497,210 would be the first time the sum is divisible by 10.

Likely, the way to attack the problem for mod 10^n, would be to ask questions about the residues of p^p (mod 10^n) in general.

 2010-12-13, 02:13 #118 davar55     May 2004 New York City 2·2,099 Posts I suppose my batteries would have been sufficient to get that first term, but for the second I would have needed my home-built multi-precision (computer-resident) calculator, written in C but currently in mothballs. Does the sum for 361649 really end in four zeros? Maybe those sums should be in the same table. This could get interesting.
2010-12-13, 02:54   #119
CRGreathouse

Aug 2006

2×2,969 Posts

Quote:
 Originally Posted by davar55 Does the sum for 361649 really end in four zeros?
Five, actually -- it will be fourth and fifth on your list:

11, 751, 1129, 361649, 361649, 12462809, 12462809, 1273183931, 1273183931.

Would someone check me on these? The repeating entries are freaking me out.

Last fiddled with by CRGreathouse on 2010-12-13 at 03:08 Reason: update list

 2010-12-13, 03:32 #120 davar55     May 2004 New York City 2×2,099 Posts Well, so far the sequence of sum(p^p)mod(10^n) (I think it needs a better name) is: 11 751 1129 361649 361649 12462809 12462809 1273183931 1273183931 Any bets that the tenth and eleventh terms are equal, and whether the twelfth breaks THAT pattern?
 2010-12-13, 03:43 #121 CRGreathouse     Aug 2006 2·2,969 Posts Nothing to 10^10.

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 42 2017-02-03 01:29 Nick Number Theory Discussion Group 0 2016-12-11 11:30 3.14159 Miscellaneous Math 12 2010-07-21 11:47 CRGreathouse Math 6 2009-11-06 19:20 m_f_h Puzzles 45 2007-06-15 17:46

All times are UTC. The time now is 23:18.

Wed Nov 25 23:18:43 UTC 2020 up 76 days, 20:29, 3 users, load averages: 1.36, 1.33, 1.32