mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-04-28, 06:23   #12
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·41·71 Posts
Default

Quote:
Originally Posted by Brian-E View Post
My guess is that a lot depends on how you implement the check of whether a number has been seen before. Obviously there are simple but very inefficient ways of doing this - and the most inefficient would take much more time than just following the chain to the end without the check. It's a non-trivial problem but I think if you try to optimize your method of checking for previous occurence you might dramatically improve the speed.
i am using a .net hashtable with the Numbers found being the keys
according to my dad who is a professional programer it is super quick
Quote:
Originally Posted by petrw1 View Post
What I would do is create a boolean array.

Every time you get a number in the sequence check the array. If it is true you have a match. Otherwise turn it to true.
i think that would use too much memory cetainly if we are trying to get to something like 1e9
i would have to use a bitarray to try that method
i will try this tonight with booleans first and the slightly slower but lots less memory using bitarray
henryzz is online now   Reply With Quote
Old 2008-04-28, 08:25   #13
robo_mojo
 
robo_mojo's Avatar
 
Mar 2008

25 Posts
Default

Quote:
Originally Posted by henryzz View Post
i am using a .net hashtable with the Numbers found being the keys
according to my dad who is a professional programer it is super quick
But not as quick as using a direct bit-array, which wouldn't require hashing, but would require memory for each potential bit.

Quote:
i think that would use too much memory cetainly if we are trying to get to something like 1e9
i would have to use a bitarray to try that method
i will try this tonight with booleans first and the slightly slower but lots less memory using bitarray
A boolean array is a bit array.
robo_mojo is offline   Reply With Quote
Old 2008-04-28, 16:39   #14
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·41·71 Posts
Default

Quote:
Originally Posted by robo_mojo View Post
A boolean array is a bit array.
not in .net
the diferences are:
bitArrays uses a huge amount less memory(i have experience of this)
when debuging u cant view the values of a bitArray but u can with booleans

it is possible to just change the declaration and it will work so debugging and memory are the only diffences
henryzz is online now   Reply With Quote
Old 2008-04-28, 19:26   #15
robo_mojo
 
robo_mojo's Avatar
 
Mar 2008

3210 Posts
Default

Quote:
Originally Posted by henryzz View Post
not in .net
the diferences are:
bitArrays uses a huge amount less memory(i have experience of this)
when debuging u cant view the values of a bitArray but u can with booleans

it is possible to just change the declaration and it will work so debugging and memory are the only diffences
What I meant was when petrw1 said "boolean array" he probably meant the same thing that you call a bit array. A bit array stores only one bit per value, and can be searched in constant time.
robo_mojo is offline   Reply With Quote
Old 2008-04-29, 22:36   #16
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

5×911 Posts
Default

Quote:
Originally Posted by robo_mojo View Post
What I meant was when petrw1 said "boolean array" he probably meant the same thing that you call a bit array. A bit array stores only one bit per value, and can be searched in constant time.
Exactly, without getting into programming language semantics I simply meant a structure where each bit represents Y or N (has the corresponding number shown up yet...or has it not.)
petrw1 is offline   Reply With Quote
Old 2008-04-30, 08:00   #17
nfortino
 
nfortino's Avatar
 
Nov 2003

2458 Posts
Default

Personally, I wouldn't bother with the bit array at all, but rather just stop checking once a number smaller than I started with is reached. If you start at 3 and go up, you are assured to be correct (in small tests this gives a speed up of a factor of ~5). Also, only bother checking with starting primes of the form 6k - 1, as primes of the form 6k +1 go straight back to a number bounded by 4k + 1 in two steps. Since this is really a question about Sophie Germain primes and Cunningham chains, any knowledge from there would apply directly here.
nfortino is offline   Reply With Quote
Old 2008-04-30, 15:37   #18
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

10110101111102 Posts
Default

[quote=nfortino;132429]Personally, I wouldn't bother with the bit array at all, but rather just stop checking once a number smaller than I started with is reached. quote]
i am already doing that
Quote:
Originally Posted by nfortino View Post
Also, only bother checking with starting primes of the form 6k - 1, as primes of the form 6k +1 go straight back to a number bounded by 4k + 1 in two steps.
i will try this later it should speed it up lots


i am in the process of speeding up the factoring and that seems to be using most of the time so that may help a lot
henryzz is online now   Reply With Quote
Old 2008-05-03, 08:23   #19
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·41·71 Posts
Default

Quote:
Originally Posted by nfortino View Post
Also, only bother checking with starting primes of the form 6k - 1, as primes of the form 6k +1 go straight back to a number bounded by 4k + 1 in two steps. Since this is really a question about Sophie Germain primes and Cunningham chains, any knowledge from there would apply directly here.
i dont understand why having a number of form 4k+1 means that it is not possible for that sequence to not eventurally become 3
also what is wrong with 5k-1 for example
henryzz is online now   Reply With Quote
Old 2008-05-03, 15:38   #20
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

7·467 Posts
Default

Quote:
Originally Posted by henryzz View Post
i dont understand why having a number of form 4k+1 means that it is not possible for that sequence to not eventurally become 3
also what is wrong with 5k-1 for example
The point is that numbers of the form 6k+1 reduce to a lower number in only two steps which, according to nfortino's method, means that you don't need to follow these chains any further.

Nothing is wrong with numbers of the form 5k-1, but nfortino is suggesting that you specifically consider the numbers modulo 6 because only the case of 5 mod 6 needs to be checked each time.

Last fiddled with by Brian-E on 2008-05-03 at 16:00
Brian-E is offline   Reply With Quote
Old 2008-05-03, 16:02   #21
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·41·71 Posts
Default

Quote:
Originally Posted by Brian-E View Post
The point is that numbers of the form 6k+1 reduce to a lower number in only two steps which, according to nfortino's method [which you say you were already implementing in which case I can't understand why you were using bit arrays at all], means that you don't need to follow these chains any further.

Nothing is wrong with numbers of the form 5k-1, but nfortino is suggesting that you specifically consider the numbers modulo 6 because only the case of 5 mod 6 needs to be checked each time.
thanks
i have taken it to 50mil and i am gonna look for other methods of finding a solution
henryzz is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primes in n-fibonacci sequence and n-step fibonacci sequence sweety439 And now for something completely different 17 2017-06-13 03:49
Aliquot sequence convergence question philmoore Math 3 2009-03-20 19:04
A New Sequence devarajkandadai Math 3 2007-03-20 19:43
Primorial Sequence Question grandpascorpion Math 2 2006-02-24 15:01
Sequence Citrix Puzzles 5 2005-09-14 23:33

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

Sun Mar 7 18:44:30 UTC 2021 up 94 days, 14:55, 1 user, load averages: 2.49, 2.21, 1.88

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.