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,857
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,857
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,857
Website

### Re: f(f(n))

I know.

'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,857
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,857
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.

'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.

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,857
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.

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,857
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,857
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,857
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,857
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