Awesome Problem

rdj5933mile5math64 · **Posted:** Fri, 11 May 2012 20:28:21 UTC

Let

and

be positive integers.

is defined inductively in the base

-recursive. We first write

in base

e.g., as a sum of terms of the form k_tn^t

, with $0 \le k_t < n$ . For each exponent

, we write

in the base

-recursive, until all the numbers in the representation are less than

. For example,

$1309 = 3^6 + 2 \cdot 3^5 + 1 \cdot 3^4 + 1 \cdot 3^2 + 1 \cdot 3 + 1$

$= 3^{2 \cdot 3} + 2 \cdot 3^{3+2} + 1 \cdot 3^{3+1} + 1 \cdot 3^2 + 1$

Let $x_1 \in \mathbb{Z}$ arbitrary. We define x_n

recursively, as following: if $x_{n-1} > 0$ , we write $x_{n-1}$ in the base

-recursive and we replace all the numbers

for

(even the exponents!), so we obtain the successor of x_n

. If $x_{n-1} = 0$ , then x_n = 0

. For example:

$x_1 = 2^{2^{2} + 2 + 1} + 2^{2+1} + 2 + 1$

$\Rightarrow x_2 = 3^{3^{3} + 3 + 1} + 3^{3+1} + 3$

$\Rightarrow x_3 = 4^{4^{4} + 4 + 1} + 4^{4+1} + 3$

$\Rightarrow x_4 = 5^{5^{5} + 5 + 1} + 5^{5+1} + 2$

$\Rightarrow x_5 = 6^{6^{6} + 6 + 1} + 6^{6+1} + 1$

$\Rightarrow x_6 = 7^{7^{7} + 7 + 1} + 7^{7+1}$

$\Rightarrow x_7 = 8^{8^{8} + 8 + 1} + 7 \cdot 8^8 + 7 \cdot 8^7 + 7 \cdot 8^6 + \dots + 7$

.
.
.

We say that the sequence "terminates" for some positive integer

, if there exists a positive integer

, such that x_N=0

when

. Find all values of

such that the sequence terminates when x_1=k

.

Hint:

Spoiler:

Denis · **Posted:** Fri, 11 May 2012 20:54:45 UTC

It gave me an awesome headache

rdj5933mile5math64 · **Posted:** Fri, 11 May 2012 23:23:19 UTC

Denis wrote:

It gave me an awesome headache

lolol this problem tends to do that

Shadow · **Posted:** Fri, 11 May 2012 23:30:00 UTC

Denis wrote:

It gave me an awesome headache

Oh come now, Denis, it's not that bad. Are you sure you're thinking about it properly?

rdj5933mile5math64 · **Posted:** Sat, 12 May 2012 00:38:33 UTC

Shadow wrote:

Denis wrote:

It gave me an awesome headache

Oh come now, Denis, it's not that bad. Are you sure you're thinking about it properly?

Finding all of the numbers (with proof) definitely wasn't easy for me. :confused:

¿...Darn am I missing something, because my solution is ridiculous...?

EDIT: or are you trolling?~ I'm not very good at knowing who's a troll and who isn't over the internet. :/

outermeasure · **Posted:** Sat, 12 May 2012 04:59:51 UTC

Shadow wrote:

Denis wrote:

It gave me an awesome headache

Oh come now, Denis, it's not that bad. Are you sure you're thinking about it properly?

Well, since Goodstein's theorem cannot be proven inside PA, unless one knows about ordinals and Cantor normal form etc. it is bound to be headaches. Indeed, if we believe PA is consistent, then PA+not(Goodstein) is also consistent and hence has a model, i.e. there exists nonstandard model of PA where Goodstein is false.

Anyway, I think OP meant $x_1\in\mathbb{N}$ , not $x_1\in\mathbb{Z}$ .

Shadow · **Posted:** Sat, 12 May 2012 07:36:56 UTC

outermeasure wrote:

Shadow wrote:

Denis wrote:

It gave me an awesome headache

Oh come now, Denis, it's not that bad. Are you sure you're thinking about it properly?

Well, since Goodstein's theorem cannot be proven inside PA, unless one knows about ordinals and Cantor normal form etc. it is bound to be headaches.

Anyway, I think OP meant $x_1\in\mathbb{N}$ , not $x_1\in\mathbb{Z}$ .

Perhaps I'm just used to slogging through things. And yes, $\mathbb{N}$ is certainly what we want.

rdj5933mile5math64 · **Posted:** Sat, 12 May 2012 18:40:17 UTC

outermeasure wrote:

Shadow wrote:

Denis wrote:

It gave me an awesome headache

Oh come now, Denis, it's not that bad. Are you sure you're thinking about it properly?

Well, since Goodstein's theorem cannot be proven inside PA, unless one knows about ordinals and Cantor normal form etc. it is bound to be headaches. Indeed, if we believe PA is consistent, then PA+not(Goodstein) is also consistent and hence has a model, i.e. there exists nonstandard model of PA where Goodstein is false.

Anyway, I think OP meant $x_1\in\mathbb{N}$ , not $x_1\in\mathbb{Z}$ .

Hmm PA is not used and x_1 is natural (sorry for the lack of tex I'm on my phone), but I'm not sure if you're seeing the solution? I don't know quite a bit of what you posted. My hint should have been

Spoiler:

Shadow · **Posted:** Sat, 12 May 2012 19:57:08 UTC

Oh really, Peano Arithmetic isn't used in a problem involving Peano Arithmetic? That would be impressive.

rdj5933mile5math64 · **Posted:** Sat, 12 May 2012 22:59:56 UTC

rdj5933mile5math64 wrote:

but I'm not sure if you're seeing the solution?

Never mind, I looked up Goodstein's Theorem. Darn. A friend gave me this problem and solution, and I thought it would be nice to share. I had no idea it was a theorem.

Shadow · **Posted:** Sat, 12 May 2012 23:15:21 UTC

rdj5933mile5math64 wrote:

but I'm not sure if you're seeing the solution?

Never mind, I looked up Goodstein's Theorem. Darn. A friend gave me this problem and solution, and I thought it would be nice to share. I had no idea it was a theorem.

Most things you've seen are probably consequences of well-known theorems, don't be bummed, it's just you don't have the experience to see it.

rdj5933mile5math64 · **Posted:** Mon, 14 May 2012 15:05:39 UTC

Shadow wrote:

rdj5933mile5math64 wrote:

but I'm not sure if you're seeing the solution?

Never mind, I looked up Goodstein's Theorem. Darn. A friend gave me this problem and solution, and I thought it would be nice to share. I had no idea it was a theorem.

Most things you've seen are probably consequences of well-known theorems, don't be bummed, it's just you don't have the experience to see it.

lol thanks, I'm sorry that the problem I gave could be bazooka'd by a theorem.

S.O.S. Mathematics CyberBoard

Awesome Problem

Who is online