20080423, 17:45  #1 
May 2004
New York City
4198_{10} Posts 
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? 
20080424, 17:29  #2  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
43×103 Posts 
Quote:
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. Last fiddled with by petrw1 on 20080424 at 17:29 

20080424, 19:30  #3 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5733_{10} Posts 
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 
20080424, 19:58  #4 
"Brian"
Jul 2007
The Netherlands
2^{6}·3·17 Posts 
I'm pessimistic. My intuition says that the problem is no easier than the 3n+1 conjecture 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.

20080424, 20:09  #5  
Jan 2006
Hungary
2^{2}·67 Posts 
Quote:
But a proof.... Willem. 

20080425, 20:25  #6 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3^{2}·7^{2}·13 Posts 
i have finished writing my programand have tested up to 10 million
does anyone have anymore suggestions of optimizations that i can implement 
20080425, 22:02  #7 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
43·103 Posts 
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. 
20080426, 07:28  #8  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3^{2}×7^{2}×13 Posts 
Quote:
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 

20080427, 17:12  #9  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
3^{2}×7^{2}×13 Posts 
Quote:
unfortunatly it only takes off a fifth of the time are there any more suggestion? 

20080427, 20:28  #10 
"Brian"
Jul 2007
The Netherlands
2^{6}·3·17 Posts 
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 nontrivial problem but I think if you try to optimize your method of checking for previous occurence you might dramatically improve the speed.
Last fiddled with by BrianE on 20080427 at 20:29 
20080428, 05:14  #11 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
43·103 Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primes in nfibonacci sequence and nstep fibonacci sequence  sweety439  And now for something completely different  17  20170613 03:49 
Aliquot sequence convergence question  philmoore  Math  3  20090320 19:04 
A New Sequence  devarajkandadai  Math  3  20070320 19:43 
Primorial Sequence Question  grandpascorpion  Math  2  20060224 15:01 
Sequence  Citrix  Puzzles  5  20050914 23:33 