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]

Advertisements

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
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: