jamie092
Badges: 11
Rep:
?
#1
Report Thread starter 6 years ago
#1
I'm really stuck on this problem. I've found the answer but I'm not sure I've done it the right way. I don't really know what recursive means. If it's finding a formula for one term to the next then I can't do it. The question is:

Name:  abc.gif
Views: 69
Size:  7.7 KB

I've got:


g(23)=g(70)+1=g(35)+2=g(106)+3=g  (53)+4=g(160)+5=g(40)+7=g(13)+6=  g(4)+5=8

Thanks for any help!
0
reply
ghostwalker
  • Study Helper
Badges: 16
#2
Report 6 years ago
#2
(Original post by jamie092)
...
See Recursion The factorial definition there is the classic example of recursion.

I think you've gone wrong in your example in going from g(40)+7 to g(13)+6.

Edit: Aside from the "+1" bit this relates to the Collatz or 3+1 conjecture
0
reply
jamie092
Badges: 11
Rep:
?
#3
Report Thread starter 6 years ago
#3
I just used g(3n+1)=g(n)-1 for that step, I can't see how that's wrong (I'm not saying it's not wrong, just that I'm not feeling very awake ^^)

Yeah I looked at that wikipedia page but I didn't really get anywhere because all other examples of recursive sequences define the nth term in terms of the (n-1)th term.

That Collatz conjecture does look interesting though, I've bookmarked it! :P
0
reply
ghostwalker
  • Study Helper
Badges: 16
#4
Report 6 years ago
#4
(Original post by jamie092)
I just used g(3n+1)=g(n)-1 for that step, I can't see how that's wrong (I'm not saying it's not wrong, just that I'm not feeling very awake ^^)
That's not something you can validly do.

If we paraphrase the definition of g(n) for n odd, it says:

g(n) is defined to be g(3n+1) + 1.

From this you cannot infer g(3n+1) is defined to be g(n) - 1

The "=" sign is perhaps misleading in this context.


Yeah I looked at that wikipedia page but I didn't really get anywhere because all other examples of recursive sequences define the nth term in terms of the (n-1)th term.

That's the basic form of recursion, the nth term is defined in terms of the (n-1)th. There is a computer algorithm further down that shows it nicely.
0
reply
jamie092
Badges: 11
Rep:
?
#5
Report Thread starter 6 years ago
#5
(Original post by ghostwalker)
That's not something you can validly do.

If we paraphrase the definition of g(n) for n odd, it says:

g(n) is defined to be g(3n+1) - 1.

From this you cannot infer g(3n+1) is defined to be g(n) + 1

The "=" sign is perhaps misleading in this context.
But if I have to use the definition that way around, then I can only calculate g(23) from terms above it i.e g(23)=g(70) +1 and then I'd have to keep going, the only way to get in terms of lower terms would be to use that g(even)=g(even/2).

I do see what you mean though I guess you can't define two things as each other.
0
reply
ghostwalker
  • Study Helper
Badges: 16
#6
Report 6 years ago
#6
(Original post by jamie092)
But if I have to use the definition that way around, then I can only calculate g(23) from terms above it i.e g(23)=g(70) +1 and then I'd have to keep going, the only way to get in terms of lower terms would be to use that g(even)=g(even/2).
That's prefectly correct.

You started at g(23) and after several steps got to g(40), which leads you to g(20), to g(10), to g(5), and then up to g(16)....

The process goes up and down, until you get to 1 - at least according to the Collatz Conjecture.
0
reply
jamie092
Badges: 11
Rep:
?
#7
Report Thread starter 6 years ago
#7
(Original post by ghostwalker)
That's prefectly correct.

You started at g(23) and after several steps got to g(40), which leads you to g(20), to g(10), to g(5), and then up to g(16)....

The process goes up and down, until you get to 1 - at least according to the Collatz Conjecture.
Ah ok then, well thanks a lot!

I got that g(2^n)=n+1 from the even part which is kind of nice. And then numbers such that n=2^m where n=3k+1 are going to be useful.

I was just wondering if that's the only way to do it, number by number, or if I can calculate a formula like T_n=f(n) or something
0
reply
ghostwalker
  • Study Helper
Badges: 16
#8
Report 6 years ago
#8
(Original post by jamie092)
Ah ok then, well thanks a lot!

I got that g(2^n)=n+1 from the even part which is kind of nice. And then numbers such that n=2^m where n=3k+1 are going to be useful.

I was just wondering if that's the only way to do it, number by number, or if I can calculate a formula like T_n=f(n) or something
A lot of work has gone into investigating the Collatz Conjecture, and as it stands, it's still a conjecture.

If you can find a formula, you'll be due an honourary Ph.D. at least, I think.
0
reply
jamie092
Badges: 11
Rep:
?
#9
Report Thread starter 6 years ago
#9
(Original post by ghostwalker)
A lot of work has gone into investigating the Collatz Conjecture, and as it stands, it's still a conjecture.

If you can find a formula, you'll be due an honourary Ph.D. at least, I think.
Haha ok, well I doubt that's happening any time soon eh =)

Thanks for the help anyway
0
reply
ghostwalker
  • Study Helper
Badges: 16
#10
Report 6 years ago
#10
(Original post by jamie092)
Haha ok, well I doubt that's happening any time soon eh =)

Thanks for the help anyway
You're welcome. There is quite a lot of information on the 'net about the conjecture and various results relating to it, if you feel so inclined.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

University open days

  • Bournemouth University
    Midwifery Open Day at Portsmouth Campus Undergraduate
    Wed, 16 Oct '19
  • Teesside University
    All faculties open Undergraduate
    Wed, 16 Oct '19
  • University of the Arts London
    London College of Fashion – Cordwainers Footwear and Bags & Accessories Undergraduate
    Wed, 16 Oct '19

How has the start of this academic year been for you?

Loving it - gonna be a great year (128)
18.21%
It's just nice to be back! (193)
27.45%
Not great so far... (251)
35.7%
I want to drop out! (131)
18.63%

Watched Threads

View All