Number Theory

Hate Number Theory · 2015-12-23 02:48:19

Start with any positive integer. If it is 1, stop. Otherwise, if it is odd, subtract 1; if it is even, divide by 2. Either way call this one step. Keep repeating steps, stopping only when you reach 1. For instance, if you start with 6, you must go 6 → 3 → 2 → 1; thus you reach 1 in 3 steps. Consider the set S10 of positive integers from which you reach 1 in exactly 10 steps. For each of the following parts, justify your answer.
a) What is the largest number in S10? The smallest?
b) How many numbers are in S10? How many even numbers?
c) What is the sum of the numbers in S10?
d) Obviously there is nothing special about 10 steps. Can you generalize your results for
Parts a–c to Sn?
e) Can you think of other questions to ask about Sn? Can you answer them, with proof? If
so do so.

I have figure out a and b, but I don't know how to prove b very well, the best I can say is that I noticed it using patterns.

Bob · 2015-12-23 04:38:26

hi Hate Number Theory

Welcome to the forum.

Noticing patterns is good, because it can lead to generalisations.

I decided to collect some more evidence by finding out the sets for S0, S1, S2 etc.

Take S2 = {3,4}

and S3 = {5,6,8}

I notice that 3 x2 = 6, 4 x 2 = 8 and 4 + 1 = 5

So I've spotted a rule here.

Thus S4 = {5x2,6x2,8x2,6+1,8+1}

That should be enough to get you going.

Bob

Hate Number Theory · 2015-12-24 03:29:22

I need help finding the sum of all the numbers in S10, I have no idea about how I should go about finding it

Bob · 2015-12-24 03:38:00

hi Hate Number Theory

The 'rule' I discovered is a term to term rule. Can you express this algebraically ?

It looks like a well known sequence and there's a general formula although I'd have to look it up.

Here's a hint for you to find it yourself:

Bob

Relentless · 2015-12-25 20:50:12

Hello! I have only just begun on this problem as I've been occupied with the festive season, but one of the first things I noticed when I listed the numbers is that the number of terms from step to step increases by a successive Fibonacci number, so it is not very difficult to find the number of terms in Sn (S2 has 2 = S1+1, S3 has 3 = S2+1, S4 has 5 = S3+2, S5 has 8 = S4+3, S6 has 13 = S5+5, S7 has 21 = S6+8, and the pattern continues). Since S1 has 1, the sums turn out to start just one term ahead of the Fibonacci sequence! So that is, so to speak, done and dusted. If you want the number of terms, just get the n+1 Fibonacci term.

The largest number is always 2^n, and that is very easy to see if you use a spreadsheet. It is also very easy to prove, as 2x > x+1 is true for x > 1.

There is actually a lot of Fibonacci in this. If you want the number of odd numbers, as you'll notice in a spreadsheet like Excel, that is Fibonacci as well, but one term behind. So you get the n-1 Fibonacci term. That makes the number of even numbers (n+1) - (n-1) which, even more simply, is just the same as the Fibonacci numbers (since that is how the Fibonacci sequence is defined!).

These aren't exactly general formulas yet, but the smallest number is 2x+1 where x is the smallest even number of Sn-2, and the smallest even number of Sn is double the smallest number from Sn-1. I suppose I'll put those two together shortly for a formula if no one else beats me to it.

The general rule for the sum seems more difficult and doesn't obey a neat explicit formula (but then, neither does Fibonacci). It seems much more difficult than everything else, in fact.

Well, it looks like I made more than a start, for all that It's an interesting set of rules!

Last edited by Relentless (2015-12-25 22:43:08)

Relentless · 2015-12-26 00:08:33

The trouble I'm having with the sums is that it's difficult to predict which odd numbers will pop up next. We know how many even and odd numbers come up, and the evens are relatively simple because they are the result of doubling... but odd numbers begin to be skipped in increasing amounts. For example, 15 does not appear in S5, but 11, 13 and 17 do. In S6, 15 appears, but 23, 27, 29 and 31 don't even though 19, 21, 25 and 33 do (and it gets much more complicated later).

The clear response is that the missing odd numbers are those that are 1 more than double a term in the previous set (or another way to put it; one more than another term in the same set). But how to account for this systematically?

If you just wanted the sum of S10, or even all the sums up to S10, that would be a simple matter, but if someone asked for the sum of S72 I could not say at the moment. A very rough approximation after S2 seems to be about 19 * (2.7)^(n-2), i.e. the sums appear to increase by a factor of roughly 2.7 (although that figure may be gradually decreasing so as to be erroneous after S15 or so).

Edit: Oh! The odd numbers that get moved up a step are those that are one more than double all of the ODD numbers in the previous step. Still don't have a formula though.

Hate Number Theory,
In case it was just the sum of S10 you were after, using Excel to speed things along I obtained the following:

Last edited by Relentless (2015-12-26 04:34:02)

Bob · 2015-12-27 23:30:27

hi Relentless,

Thanks for joining in. I was doubting my analysis that this was Fibonacci so I'm grateful that you think so too. Here's what I have so far:

Let's say that Sn contains a number, a , whose sequence is a,b,c,d,e,...,1

b must be in Sn-1.

Let's consider the numbers in Sn-1.

If b is odd it couldn't have come from b = a-1 because that would require that a is odd, in which case a-1 is even.

So b would have to come from a/2.

If b is even, it could have come from b = a/2

But it could also have come from b = a-1

So all numbers in Sn can be generated from Sn-1 by doubling all the numbers in Sn-1 and also adding one to any even numbers.

example to make this clear

S4 - {7, 9, 10, 12, 16}

Double these: 14, 18, 20, 24, 32

Add 1 to the evens: 11, 13, 17

Thus

S6 = {11, 13, 14, 17, 18, 20, 24, 32}

S4 has 2 odds and 3 evens
S5 has 3 odds and (2+3) evens.

Generalising if Sn-1 has x odds and y evens,

then Sn has y odds and (x+y) evens.

and the total number of elements is x + 2y

Sn+1 has (x+y) odds and (x + 2y) evens

So these numbers increase according to the Fibonacci rule

odds 1, 0, 1, 1, 2, 3, 5, 8, ...
evens 0, 1, 1, 2, 3, 5, 8, ....
total 1, 1, 2, 3, 5, 8, 13, ....

1
2
3,4
5,6,8
7,9,10,12,16
11,13, 17, 14,18,20,24,32

Now to look at the actual numbers and totals of their values.

Bob

Relentless · 2015-12-28 00:10:12

I think your reasoning is perfectly sound, and deducible from the rules given that
1. The number of even terms is the nth Fibonacci number
2. The number of odd terms is the n-1 Fibonacci number, and
3. The total number of terms is the n+1 Fibonacci number
For any given Sn.

Just to confirm, I will call a Fibonacci number that corresponds to the step number Fn, and restate exactly what you said in those terms.
Sn-1 has Fn-2 odds and Fn-1 evens.
Then Sn has Fn-1 odds and Fn = Fn-2 + Fn-1 evens,
The total number of elements being Fn+1 = Fn-2 + 2Fn-1
Sn+1 has Fn = Fn-2 + Fn-1 odds and Fn+1 = Fn-2 + 2Fn-1 evens

To slightly correct your running counts, it goes:
Odds: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
Evens: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
Total: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

As far as I'm concerned, the only outstanding problem is how to obtain a general formula for the sum (there is also a little problem of obtaining a general formula for the smallest number, but that should be pretty easy). Everything else is toast by now, and it all has to do with Fibonacci.

Last edited by Relentless (2015-12-28 00:43:23)

Bob · 2015-12-28 07:48:41

hi Relentless

To slightly correct your running counts, ...

I was being a bit casual about low values of n as it only works properly once you get past S1 = {2} but I was counting from S0.

Anyway I've made progress with the lowest elements.

Your formula "smallest number is 2x+1" gives the calculation to go from Sn-1 to Sn+1. I've converted it to a formula for generating any lowest value element.

Because the term to term rule jumps across Sn, you need two separate formulas to cover n even and n odd. Here they are:

n odd:

and n even:

I can generate each number total as well but only with a term to term rule and with given Fibonacci numbers. So it will take a bit of research before I can come up with a general formula. (if ever }

Bob

Relentless · 2015-12-28 22:14:36

Hi bob;

I have confirmed your formulas for sets up to S20, which is ample confirmation.

I suspect that I will give this problem another good go quite soon, but not just yet. In the meantime, though, I have brute force calculated all of the sums up to and including S20 for scrutiny, which was a big task in itself.

S1: 2
S2: 7
S3: 19
S4: 54
S5: 149
S6: 411
S7: 1128
S8: 3091
S9: 8459
S10: 23,134
S11: 63,241
S12: 172,839
S13: 472,304
S14: 1,290,519
S15: 3,526,023
S16: 9,633,694
S17: 26,320,421
S18: 71,909,827
S19: 196,463,080
S20: 536,749,995

Notice the ratios. They appear to converge to a number roughly 2.732076. Can this number, or a number slightly below it, be connected to Fibonacci? Or is it something else altogether? (The best I've got is that phi^2 ~ 2.618033989)

Last edited by Relentless (2015-12-29 00:06:05)

bobbym · 2015-12-28 23:59:44

Hi;

Could you please recheck your S20. I believe it should be 536749995.

Relentless · 2015-12-29 00:04:59

Hello! You are right! Thank you I had accidentally counted the smallest term a second time after I identified it.

Any luck with the rule?

Last edited by Relentless (2015-12-29 00:05:35)

bobbym · 2015-12-29 00:08:15

If you mean a rule for your column of numbers, then yes!

Relentless · 2015-12-29 00:22:59

I mean the rule for calculating the sum of the numbers in Sn

I don't know about you, but I got S20 with a lot of copy/pasting.

Last edited by Relentless (2015-12-29 00:23:54)

bobbym · 2015-12-29 00:28:44

Hi;

There is such a rule, using it I get

as the ratio.

Relentless · 2015-12-29 00:51:07

Hm... Well I personally prefer full disclosure, but if required I will foolishly follow my own methods while you move on to greater things like predicting the nth decimal point of pi to the pi or something.

bobbym · 2015-12-29 01:31:46

I like full disclosure to add something but in this case it does not.

Relentless · 2015-12-29 01:47:38

Well it saved me a bit of futile work, since my mathematical knowledge is currently insufficient to ever derive that ghastly thing. xD

bobbym · 2015-12-29 01:58:33

The work would not be futile but it might be difficult.

The formula given is one that is empirically based. It could be false but it is probably true, hopefully to a high probability. Such formulas allow us to use classical methods in the other direction, instead of using them to find the answer, they are used to back engineer from the answer to a proof. Much like Mr Wong did in the other thread.

Relentless · 2015-12-29 02:05:30

I like the idea of zeroing in on an answer very much. Why can you not specify what the probability of it being true is?

And for a bit of fun, an answer with this formula can be given to the hypothetical question in post #6: What is the sum of S72?
According to the formula, it is: 26,741,856,567,998,641,197,432,083,722,543 or about 26.7 nonillion.

The largest term is 4,722,366,482,869,645,213,696 or about 4.7 sextillion.
The smallest term is 137,438,953,471 or about 137.4 billion.

It has 806,515,533,049,393 or about 806.5 trillion terms.
498,454,011,879,264 or about 498.45 trillion of them are even.
308,061,521,170,129 or about 308 trillion of them are odd.

Furthermore, the average term is about 33 quadrillion.

Last edited by Relentless (2015-12-29 02:18:55)

bobbym · 2015-12-29 02:39:48

Why can you not specify what the probability of it being true is?

Bertrand Russell wrote:

I wanted certainty in the kind of way in which people want religious faith. I thought that certainty is more likely to be found in mathematics than anywhere . . . .

Mathematicians are a curious bunch. Adherents to Pure Math argue that the Applied math guys are not doing math while the Applied guys say the Pure guys are not doing anything at all. The latest bunch to step into the battle are the Experimental guys. They point out how successful physics is and berate the Pure and Applied camps for abandoning modes of thinking that Newton and Gauss used. The ability to experiment pretty much died with Cauchy and math became what it is today.

Experimental math allows one to get more answers but sometimes at the cost of certainty. Like the physicist we can only say the answers are probably to a very high degree correct. The probability of it being correct is a subjective one and in this case difficult to pin down. You will recognize the analogy with modern QM where we can get one thing but then can not get the other.

I like the idea of zeroing in on an answer very much.

Computation is in the blood. Math types hate it and consider it inferior, physicists love it but do not know how. The answer... the EM guys!

Hate Number Theory · 2015-12-29 15:17:59

I'm still confused on a general rule for the sums of the sets of Sn. Can somebody explain that in depth to me? Otherwise, thanks for everything, you guys helped me so much!

bobbym · 2015-12-29 15:37:31

If you need this for an assignment then very likely it is not applicable.

1) Generate lots of data. Post #10.

2) Apply the methods of experimental math to that data. Post #17.

Relentless · 2015-12-29 18:49:58

Hello, I cannot exactly give an in-depth explanation, but basically I used a lot of doubling and adding 1 in Excel to generate all of the sets up to S20, summed each of them, and posted the sums so somebody else could have a look at them before I came back to the problem of the general rule for the sums.

Then bobbym waved his experimental wand on the numbers, and we get the long rule in post #17, which, I have confirmed, does in fact work for the sums that I have. It is obviously not meant for an assignment, considering that every other question was quite straightforward but the rule for the sum of Sn is that thing.
If you were after a proof for that rule in #17, it is my understanding that it is unproven, but confirmed to an uncertain but high probability.

Last edited by Relentless (2015-12-29 18:52:18)

Bob · 2016-01-02 07:47:17

hi

Been away for the New Year so I haven't had a chance to post until now.

Here's my latest analysis. (sorry bobbym, but this involves some pure maths )

On is the odd total, En the even total and Tn the grand total. fn is the nth Fibonacci number.

Using my earlier rules:

and

Therefore

As

this is beginning to look like bobbym's EM formula and could be easily proved by showing the EM version fits this version. I'll let someone with M have a go at that!

Bob

Math Is Fun Forum

#1 2015-12-23 02:48:19

Number Theory

#2 2015-12-23 04:38:26

Re: Number Theory

#3 2015-12-24 03:29:22

Re: Number Theory

#4 2015-12-24 03:38:00

Re: Number Theory

#5 2015-12-25 20:50:12

Re: Number Theory

#6 2015-12-26 00:08:33

Re: Number Theory

#7 2015-12-27 23:30:27

Re: Number Theory

#8 2015-12-28 00:10:12

Re: Number Theory

#9 2015-12-28 07:48:41

Re: Number Theory

#10 2015-12-28 22:14:36

Re: Number Theory

#11 2015-12-28 23:59:44

Re: Number Theory

#12 2015-12-29 00:04:59

Re: Number Theory

#13 2015-12-29 00:08:15

Re: Number Theory

#14 2015-12-29 00:22:59

Re: Number Theory

#15 2015-12-29 00:28:44

Re: Number Theory

#16 2015-12-29 00:51:07

Re: Number Theory

#17 2015-12-29 01:31:46

Re: Number Theory

#18 2015-12-29 01:47:38

Re: Number Theory

#19 2015-12-29 01:58:33

Re: Number Theory

#20 2015-12-29 02:05:30

Re: Number Theory

#21 2015-12-29 02:39:48

Re: Number Theory

#22 2015-12-29 15:17:59

Re: Number Theory

#23 2015-12-29 15:37:31

Re: Number Theory

#24 2015-12-29 18:49:58

Re: Number Theory

#25 2016-01-02 07:47:17

Re: Number Theory

Board footer