Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2014-09-01 05:44:59

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

f(f(n))

f: N -> N is a strictly increasing function such that f(f(n))=3n

What is the value of f(2001)?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#2 2014-09-01 07:09:54

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2014-09-01 12:20:55

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

Re: f(f(n))

How?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#4 2014-09-02 00:12:51

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2014-09-02 00:42:55

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

Re: f(f(n))

I know.

Further information, please?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#6 2014-09-02 00:55:23

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

Using the problem itself (RIPOSTP) we can get a bunch of values

{2, 3, 6, 7, 8, 9, 12, 15, 18, 19, 20,...} for n = 1, 2, 3...

Now we just use EM.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2014-09-02 02:15:55

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: f(f(n))

Hi Agnishom.

Let me try. We have

.

As f is strictly increasing, we must have
. It can’t be 1 otherwise
. It can’t be 3 either otherwise
so
which is impossible for a strictly increasing function. Therefore:

by strict-increasingness.

Now note that
. This gives
and
and if
then
while if
then
Thus
and
. Thus
.

Last edited by Olinguito (2014-09-02 10:50:33)


Bassaricyon neblina

Offline

#8 2014-09-02 02:45:58

ElainaVW
Member
Registered: 2013-04-29
Posts: 580

Re: f(f(n))

Anyone able to attack this problem head on by figuring what f(n) is. No piecewise functions, just one expression?

Offline

#9 2014-09-02 02:57:01

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

Re: f(f(n))

Olinguito wrote:

This gives

and
and if
then
while if
then

I don't get this. How do you get this?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#10 2014-09-02 09:56:56

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

Hi;

Anyone able to attack this problem head on by figuring what f(n) is.

To some extent that can be done. It leads to the following rote procedure for the solution.

We expand on Michael Somos' answer and continue it. He provides 3 recurrences,

Using these we can recursively solve the problem by redefining it in terms of easier quantities.

Cleaning it up we get:

Now remembering our sequence,

you can see that a(1) = 2 and a(2) = 3 so

Looks complicated but it is just substitutions until the whole problem is defined in terms of the first two terms. I deliberately did not simplify each expression to make it easier to see the tree.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#11 2014-09-02 10:09:03

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: f(f(n))

Agnishom wrote:
Olinguito wrote:

This gives

and
and if
then
while if
then

I don't get this. How do you get this?

and
come from
; they can be proved by induction.

Note that there are
integers strictly between
and
, and also
integers strictly between

and

Hence, by strict-increasingness,
for
. Get it? Put another way:

  • If there are m integers strictly between a and b and m integers strictly between f((a) and f(b) and f is strictly increasing, then f(a + r) = f(a) + r for 1 ≤ rm,

Hence
.

Similarly you can show that if
then
– but you don’t need this bit to calculate
.

Last edited by Olinguito (2014-09-02 10:50:12)


Bassaricyon neblina

Offline

#12 2014-09-02 12:31:04

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

Re: f(f(n))

bobbym wrote:

Hi;

Anyone able to attack this problem head on by figuring what f(n) is.

To some extent that can be done. It leads to the following rote procedure for the solution.

We expand on M Somos's answer and continue it. He provides 3 recurrences,

Using these we can recursively solve the problem by redefining it in terms of easier quantities.

Cleaning it up we get:

Now remembering our sequence,

you can see that a(1) = 2 and a(2) = 3 so

Looks complicated but it is just substitutions until the whole problem is defined in terms of the first two terms. I deliberately did not simplify each expression to make it easier to see the tree.

your code, please?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#13 2014-09-03 02:12:05

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

There is no code. That was done by hand with a pen. It requires no mathematics at all, just arithmetic on the first 2 initial conditions. M Somos made it easy but EVW was also able to derive his recurrences.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#14 2014-09-03 03:53:45

Olinguito
Member
Registered: 2014-08-12
Posts: 649

Re: f(f(n))

I didn’t realize this was supposed to be a computer question and solved it the hard way. sad


Bassaricyon neblina

Offline

#15 2014-09-03 03:55:54

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

This is not a computer answer. It was done by pen and paper in the manner shown. The only requirement is arithmetic. See post #13


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#16 2014-09-03 03:57:39

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

Re: f(f(n))

Olinguito wrote:

I didn’t realize this was supposed to be a computer question and solved it the hard way. sad


I like your solution very much except that a solution is simpler when you can program it. (opinion 37)


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#17 2014-09-03 03:59:26

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

It took 5 minutes and 30 minutes to latex it by hand.

Regarding Opinion #37:

DZ wrote:

You would realize that you REALLY understand something ONLY after you PROGRAMED it YOURSELF.

But as I have said repeatedly my working here is not computer related.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#18 2014-09-03 04:29:12

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

Re: f(f(n))

M has an option to copy latex

I do not understand integer addition. I cannot program it.


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#19 2014-09-03 04:36:37

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

I am using M's much vaunted latex capabilities. I have even modified them. But latex as he sees it and latex on the forum are not the same things.

I do not understand integer addition. I cannot program it.

You do not understand it, you just think you do.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#20 2014-09-03 04:41:48

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

Re: f(f(n))

All my programs are based on addition, so I understand nothing?


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#21 2014-09-03 04:44:11

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

It is possible to use words and concepts that you do not fully understand, effectively. If humanity were required to have perfect understanding of things we would not exist. God would have made something better. Obviously perfect understanding or even a good understanding is not necessary for survival in math or life. See my signature.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#22 2014-09-03 04:47:05

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

Re: f(f(n))

There are people who can program integer addition. E.g, bobbym


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#23 2014-09-03 04:52:08

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

I can program integer addition even multiprecision on very primitive machines but I do not understand many things about it. I think humans get caught up in a very simple trap. Let us say that person A is a lot smarter than most of the other humans. Soon A becomes pride filled. A forgets that just because he/she is superior to other humans does not imply great intelligence or abilities.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#24 2014-09-03 04:54:02

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,806
Website

Re: f(f(n))

What is J-rod?

The person below is C


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#25 2014-09-03 04:56:03

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: f(f(n))

We are getting way off the topic. Were you able to follow my solution?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB