# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1235: Power struggle

From New Scientist #2391, 19th April 2003 [link]

I have just given a class of students an interesting exercise. I wrote on the board the exact form of a particular number. Then I asked the class to calculate the sum of that number with its own reciprocal. They all got the correct whole number answer.

Then I asked the first student to square the original number and add that square to its own reciprocal. I asked the next student to cube the original number and add that cube to its own reciprocal. And so on around the class, increasing the power by one each time.

One of the students’ answers was 123.

What was the next student’s answer after that?

[enigma1235]

### 3 responses to “Enigma 1235: Power struggle”

1. Jim Randell 7 May 2015 at 8:42 am

Let’s suppose the number in question is x, and the sum of it and its reciprocal is some integer n.

x + 1/x = n

We note that, for a fixed n, if x is a solution to this equation then 1/x is also a solution, and this can be rewritten as a quadratic equation (x ≠ 0), so these are the only two solutions.

If x ≠ 1 then one of these solutions will be larger than 1 and one will be smaller than 1.

The teacher then asks the class to consider the expression:

S(k) = (x^k) + 1/(x^k)

We note that S(0) = 2, and S(1) = n.

Now consider:

((x^k) + 1/(x^k)) × (x + 1/x) = S(k) × S(1) = S(k) × n
((x^(k + 1)) + 1/(x^(k+1))) + ((x^(k – 1)) + 1/(x^(k – 1))) = S(k + 1) + S(k – 1) = S(k) × n

So we have the recurrence relation:

S(k + 1) = S(k) × n – S(k – 1)

This Python program uses this relation to generate possible sequences that include 123. It runs in 32ms.

```from enigma import irange, printf

for n in irange(3, 123):
S = [2, n]
while S[-2] < 123:
s = n * S[-1] - S[-2]
S.append(s)
if S[-2] == 123:
printf("n={n} S={S}")
```

Solution: The next student’s answer is 322.

The sequence in this case is: S(0) = 2, S(1) = 3, S(2) = 7, S(3) = 18, S(4) = 47, S(5) = 123, S(6) = 322.

So the student that got 123 is dealing with fifth powers, and the student that got 322 is dealing with sixth powers.

The number x in this case is a solution to:

x + 1/x = 3

so:

x = (3 ± √5) / 2

The other sequence that contains 123 is when S(1) = 123. And in this case the next number in the sequence is S(2) = 15127. But the question implies that 123 is not the answer to S(1) (or, indeed, S(2) or S(3)), so we can discard this solution.

• Hugh Casement 7 May 2015 at 3:36 pm

Your x looks familiar, Jim.  The larger value is phi² = 1 + phi, the smaller is of course its reciprocal but also equals (phi – 1)² = 2 – phi, where phi is the golden ratio.
The recurrence relation certainly saves a lot of slog.

2. Brian Gladman 7 May 2015 at 4:13 pm
```# -*- coding: utf8 -*-

from itertools import count
from functools import reduce
from operator import mul

def nCr(n, r):
r = min(r, n - r)
return (reduce(mul, range(n, n - r, -1)) //
reduce(mul, range(1, r + 1))) if r else 1

# Expand with N = (x + 1/x), expand (x + 1/x)^k using the binomial theorem:
#
#  (x + 1/x)^k = C(0, k).[x^k + 1/x^k] + C(1, k).[x^(k - 2) + 1/x^(k - 2)]
#              + C(2, k).[x^(k - 4) + 1/x^(k - 4)] + ...
#
# Hence with S[k] = (x^k + 1/x^k):
#
#   S[k] = (x + 1/x)^k - C(1, k).S[k - 2] - C(2, k).S[k - 4] - ...
#        = N^k - sum[C(i, k).S[k - 2.i], i = 1 .. k // 2]
#
# So we can compute S[k] iteratively (also, since x = {N ± √(N^2 - 4)}/2
# we know that N >= 3)

# N is the integer sum of the number and its reciprocal
for N in count(3):
# the list for the S[k] values
seq = [1, N]
# k is the power being considered
for k in count(2):
t = N ** k
for i in range(1, k // 2 + 1):
t -= nCr(k, i) * seq[k - 2 * i]
seq += [t]
if seq[-2] >= 123:
break
if seq[-2] == 123:
print(seq[-1], tuple(seq))
break
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.