mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-04-23, 17:45   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

2·2,099 Posts
Default 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?
davar55 is offline   Reply With Quote
Old 2008-04-24, 17:29   #2
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

17×263 Posts
Default

Quote:
The question is: does every N eventually evolve into this cycle?
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.

Last fiddled with by petrw1 on 2008-04-24 at 17:29
petrw1 is online now   Reply With Quote
Old 2008-04-24, 19:30   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

167716 Posts
Default

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
henryzz is offline   Reply With Quote
Old 2008-04-24, 19:58   #4
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

5×653 Posts
Default

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.
Brian-E is offline   Reply With Quote
Old 2008-04-24, 20:09   #5
Siemelink
 
Siemelink's Avatar
 
Jan 2006
Hungary

22·67 Posts
Default

Quote:
Originally Posted by henryzz View Post
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
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.
Siemelink is offline   Reply With Quote
Old 2008-04-25, 20:25   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

34·71 Posts
Default

i have finished writing my programand have tested up to 10 million
does anyone have anymore suggestions of optimizations that i can implement
henryzz is offline   Reply With Quote
Old 2008-04-25, 22:02   #7
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

17×263 Posts
Default

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.
petrw1 is online now   Reply With Quote
Old 2008-04-26, 07:28   #8
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

34·71 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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.
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
henryzz is offline   Reply With Quote
Old 2008-04-27, 17:12   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

34·71 Posts
Default

Quote:
Originally Posted by petrw1 View Post
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.
i have programed this
unfortunatly it only takes off a fifth of the time
are there any more suggestion?
henryzz is offline   Reply With Quote
Old 2008-04-27, 20:28   #10
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

63018 Posts
Default

Quote:
Originally Posted by henryzz View Post
i have programed this
unfortunatly it only takes off a fifth of the time
are there any more suggestion?
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.

Last fiddled with by Brian-E on 2008-04-27 at 20:29
Brian-E is offline   Reply With Quote
Old 2008-04-28, 05:14   #11
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

17·263 Posts
Default

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.
petrw1 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 02:41.

Tue Dec 1 02:41:34 UTC 2020 up 81 days, 23:52, 1 user, load averages: 1.47, 1.70, 1.83

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.