mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2010-03-30, 17:27   #23
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by bsquared View Post
I guess I was thinking of a link to tables, or something. But that would require me to generate and host those tables. I'll save that for some day when I'm bored ;)
Maybe you can submit a sequence of every millionth term or something. Not exactly classy, but it has precedent (A080128, say).

76304519151822049179, 671924965564646162227, 2393465488665494654963, 5889405149040404480379, 11834774513923727795971, 20925456417823033330259, ...
CRGreathouse is offline   Reply With Quote
Old 2010-03-30, 19:00   #24
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13×257 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Right. You could do two modili at a time without much penalty, though, with appropriate lookup tables and bit operations. Note that you only need to compare (and hence reduce) every 8 primes, each term (other than the first) has index = 5 (mod 8).
I just realized my code to do the sum of prime squares routines was hugely inefficient, in that I was using YAFU's built in arbitrary precision functions to do the squaring and summing. In reality we only need fixed precision of, say, 3 64 bit limbs (192 bits should be plenty to represent the sum). Implementing this made my sum of prime squares routine about 35 times faster.

I also store the highest power of 2 dividing the power of 10 modulus, which makes for a very quick pre-test of divisibility by 10 (logical AND followed by a predictable branch) and makes full precision divisions *extremely* rare. Doing things this way is actually faster than using pure modular arithmetic, since we almost never have to perform a division.

As a side benefit, it's easy to build tables of prime sums, or prime square sums, and we also don't have to restart a sum to test for a new power of 10 modulus.
bsquared is offline   Reply With Quote
Old 2010-03-30, 19:02   #25
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Not exactly classy ...
Right up my alley, then
bsquared is offline   Reply With Quote
Old 2010-03-30, 19:43   #26
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

64158 Posts
Default

I must have some sort of tinkerers disease... can't leave well enough alone.

This disease was causing me to be offended by how long it was taking to compute the primes in a range of 1e9. So I tinkered... and doubled the speed

before:
Code:
found 40609038 primes in range 49000000000 to 50000000000 in elapsed time = 5.4835
**** 49460594569 is 0 mod 1410065408 ****
sum of squares complete in elapsed time = 6.8852, sum is 1714863031171407826702942323341
after:
Code:
found 40609038 primes in range 49000000000 to 50000000000 in elapsed time = 2.8866
**** 49460594569 is 0 mod 10000000000 ****
sum of squares complete in elapsed time = 0.1639, sum is 1714863031171407826702942323341
which of course is completely useless, but now I feel better.
bsquared is offline   Reply With Quote
Old 2010-03-30, 20:00   #27
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default

This is fine work by all of you. If you wish to submit the sequence to
oeis, please go ahead. I couldn't do justice to the calculations, which
I'm really impressed by. Joint discovery (attribution) is fine.
davar55 is offline   Reply With Quote
Old 2010-03-30, 20:14   #28
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by davar55 View Post
I couldn't do justice to the calculations, which
I'm really impressed by.
I'll echo this. I just used a one-line Pari script to discover mine.
CRGreathouse is offline   Reply With Quote
Old 2010-04-02, 14:41   #29
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Now in OEIS: A174862
bsquared is offline   Reply With Quote
Old 2010-04-06, 20:28   #30
davar55
 
davar55's Avatar
 
May 2004
New York City

419810 Posts
Default

With all the work done on the OP, it shouldn't be too hard
to generalize the problem a bit.

I think cubes.

2^3 + 3^3 + 5^3 + ... + p^3 = 10mK

What is the smallest prime p such that
the sum of cubes of all primes up to p
is a multiple of 10 (or 100 or 1000 or 10000 or ...).

I'm also curious about how these (squares and cubes) results
compare to first powers (sum of primes themselves).

Since these series depend on the properties of a number
in base ten, they could be considered recreational --
interesting but not necessarily useful. Still, perhaps the
sequence of sequences can someday be used to derive some
important number theoretic fact. That's one of the purposes
of the oeis.
davar55 is offline   Reply With Quote
Old 2010-04-06, 22:33   #31
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

4,457 Posts
Default

Quote:
Originally Posted by davar55 View Post
I'm also curious about how these (squares and cubes) results compare to first powers (sum of primes themselves).
A start on the first powers for the first 6,000,000 primes - p<=104,395,301

5 10
23 100
35677 63731000
106853 515530000
632501 15570900000

Last fiddled with by petrw1 on 2010-04-06 at 22:40 Reason: 6M
petrw1 is offline   Reply With Quote
Old 2010-04-06, 22:36   #32
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

13·257 Posts
Default

Quote:
Originally Posted by petrw1 View Post
A start on the first powers for the first 1,000,000 primes - p<=15,485,863

5 10
23 100
35677 63731000
106853 515530000
632501 15570900000
See here
bsquared is offline   Reply With Quote
Old 2010-04-06, 22:44   #33
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

4,457 Posts
Default

Quote:
Originally Posted by bsquared View Post
See here
Cool....my first 5 answers match.

Crap...I missed the next 2: Bug alert!
petrw1 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Regarding Squares a1call Miscellaneous Math 42 2017-02-03 01:29
Basic Number Theory 12: sums of two squares Nick Number Theory Discussion Group 0 2016-12-11 11:30
Integers = sums of 2s and 3s. 3.14159 Miscellaneous Math 12 2010-07-21 11:47
Sums of three squares CRGreathouse Math 6 2009-11-06 19:20
squares or not squares m_f_h Puzzles 45 2007-06-15 17:46

All times are UTC. The time now is 16:09.

Tue Nov 24 16:09:28 UTC 2020 up 75 days, 13:20, 4 users, load averages: 1.45, 1.68, 1.70

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.