Sequence Question
 

(In the spirit of the 3N+1 sequence question...)

Start with any positive integer N.

If N is prime (or 1) replace it with 2N+1.
If N is composite, replace it with its largest prime factor.
Repeat these steps.

For example, if N=3 we get the cycle
3 -> 7 -> 15 -> 5 -> 11 -> 23 -> 47 -> 95 -> 19 -> 39 -> 13 -> 27 -> 3.

The question is: does every N eventually evolve into this cycle?

[QUOTE] The question is: does every N eventually evolve into this cycle?[/QUOTE]

Can I just reply with: "Yes"

And if you ask "How do you know?" or "Can you prove it?" ... I would have to reply with: "I don't" and "No".

Just intuition.

i have done all up to 20 by hand and they all go into the same sequence
i strongly suspect that the answer is yes
i am just about to write a quick program to search for another sequence

I'm pessimistic. My intuition says that the problem is no easier than the [URL="http://en.wikipedia.org/wiki/Collatz_conjecture"]3n+1 conjecture[/URL] to which davar55 refers and therefore - unless someone can find a second cycle by searching - it will not be solvable with currently known techniques. Even if a second cycle is found and maybe others too, we still won't be able to prove that all numbers reduce to one of these cycles.

[QUOTE=henryzz;132132]i have done all up to 20 by hand and they all go into the same sequence
i strongly suspect that the answer is yes
i am just about to write a quick program to search for another sequence[/QUOTE]

You only have start with the primes. As soon as the factor is smaller then your start prime you're done. This is likely to happen quickly, especially when your test candidate has multiple factors.
But a proof....

Willem.

i have finished writing my programand have tested up to 10 million
does anyone have anymore suggestions of optimizations that i can implement

I would consider saving in an array all numbers (prime or otherwise) encountered so far. Whenever your current chain matches one of those you can skip to the next chain knowing it will eventually end in 3.

I suspect that most will abort a lot sooner.

I believe the astutue programmers call this memoization.

[quote=petrw1;132194]I would consider saving in an array all numbers (prime or otherwise) encountered so far. Whenever your current chain matches one of those you can skip to the next chain knowing it will eventually end in 3.

I suspect that most will abort a lot sooner.

I believe the astutue programmers call this memoization.[/quote]
when i last posted i had one idea and it was that
i am going to my grandmother's 80th birthday meal 2day and i wont be back until 2morrow lunch time
i will program it then

[quote=petrw1;132194]I would consider saving in an array all numbers (prime or otherwise) encountered so far. Whenever your current chain matches one of those you can skip to the next chain knowing it will eventually end in 3.

I suspect that most will abort a lot sooner.

I believe the astutue programmers call this memoization.[/quote]
i have programed this :smile:
unfortunatly it only takes off a fifth of the time:mad:
are there any more suggestion?

[quote=henryzz;132247]i have programed this :smile:
unfortunatly it only takes off a fifth of the time:mad:
are there any more suggestion?[/quote]
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.

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.

[quote=Brian-E;132257]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.[/quote]
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=petrw1;132268]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.[/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

[quote=henryzz;132272]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]
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[/quote]
A boolean array is a bit array.

[quote=robo_mojo;132275]
A boolean array is a bit array.[/quote]
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

[quote=henryzz;132308]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[/quote]
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.

[QUOTE=robo_mojo;132323]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.[/QUOTE]

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.)

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.

[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=nfortino;132429]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.[/quote]
i will try this later it should speed it up lots:smile:


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

[quote=nfortino;132429]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.[/quote]
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

[quote=henryzz;132643]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[/quote]
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.

[quote=Brian-E;132656]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 [[I]which you say you were already implementing in which case I can't understand why you were using bit arrays at all[/I]], 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.[/quote]
thanks
i have taken it to 50mil and i am gonna look for other methods of finding a solution