Enigmatic Code

Programming Enigma Puzzles

Enigma 642: Fibonacciesque

From New Scientist #1796, 23rd November 1991 [link]

My children had been practising addition, forming additive sequences of numbers, and when the numbers got too large for them, extending the sequence the other way using subtraction and getting some negative numbers. Eventually, they noticed that one of their sequences had numbers in it divisible by 2, 3, 5 and 7 but none divisible by 11. Part of that sequence was:

…  –2  3  1  4  …

the rule going from left to right being, of course, that one term plus the following one gives the next.

The children soon saw too that every sequence they wrote down had terms divisible by 2 and 3, and probably 7 also.

What I want you to find is the two sequences like this, each having no terms divisible by 5, 11 or 13. In each sequence the four consecutive terms we want should have:

just the first term negative;
the third term 3;
and the fourth term less than 100.

(In fact, one of the sequences will have terms divisible by 17 and none divisible by 19, while the other will have terms divisible by 19 and none divisible by 17, but you don’t need these facts to find them).

Find the four terms of the two sequences.

[enigma642]

8 responses to “Enigma 642: Fibonacciesque

  1. Jim Randell 8 October 2021 at 8:30 am

    If the second term is a, and the third term is b, then the start of the sequence looks like:

    (b – a), (a), (b), (a + b), …

    We are looking for sequences where (b – a) is negative (i.e. a > b).

    And b = 3.

    And (a + b) < 100.

    So, we have:

    b = 3
    3 < a < 97

    This Python program examines terms of candidate sequences, removing those that have terms divisible by 5, 11, or 13, until there are only 2 sequences remaining. It runs in 55ms.

    Run: [ @replit ]

    from enigma import irange, fib, first, printf
    
    # candidate sequences by the first 2 terms
    ss = dict()
    b = 3
    for a in irange(4, 96):
      k = (b - a, a)
      ss[k] = fib(*k)
    
    # consider terms in the sequences, until we only have 2 candidate remaining
    while len(ss.keys()) > 2:
      # remove any sequence with a term divisible by 5, 11, 13
      ks = list()
      for (k, v) in ss.items():
        n = next(v)
        if any(n % d == 0 for d in (5, 11, 13)):
          ks.append(k)
      for k in ks: del ss[k]
    
    # output the first 4 terms of each remaining sequence
    for k in ss.keys():
      ts = first(fib(*k), 4)
      printf("{ts} ...")
    

    Solution: The two sequences start: (–28, 31, 3, 34) and (–73, 76, 3, 79).

    (The published solution gives 6 as the third term in the second sequence, but this must be an error in the solution, as the third term is required to be 3).

    • Frits 8 October 2021 at 1:18 pm

      @Jim, the problem for me is a bit ambiguous.

      If I have problems adding numbers bigger than fi 400 then there are probably more solutions (like -48, 51, 3, 54). So the solution depends on this limit (and if you swap back to adding again?).

      You only say “if there are two such sequences it must be A and B”. There is no check whether if the sequence is continued (up to infinity?) for A and B no divisibility by 5, 11 or 13 may arise.

      • Jim Randell 8 October 2021 at 1:43 pm

        @Frits: As I can’t test all terms in a sequence programmatically, I treated the statement that there are exactly two sequences as described that have no terms divisible by 5, 11 or 13, as a fact.

        So all I need to do is eliminate all the other sequences, and the two that remain must be the two I’m looking for. And that is what my program does.

        It is easy to check that first 50,000 terms or so of these sequences programmatically, but to show all terms are not divisible would require a mathematical proof. (Like Teaser 683).

      • Jim Randell 8 October 2021 at 2:29 pm

        I had a look at the behaviour of these sequences mod 5, 11, 13 and we get patterns that repeat as follows. For (–73, 76):

        mod 5: [2, 1, 3, 4] …
        mod 11: [4, 10, 3, 2, 5, 7, 1, 8, 9, 6] …
        mod 13: [5, 11, 3, 1, 4, 5, 9, 1, 10, 11, 8, 6, 1, 7, 8, 2, 10, 12, 9, 8, 4, 12, 3, 2, 5, 7, 12, 6] …

        And for (–28, 31):

        mod 5: [2, 1, 3, 4] …
        mod 11: [5, 9, 3, 1, 4] …
        mod 13: [11, 5, 3, 8, 11, 6, 4, 10, 1, 11, 12, 10, 9, 6, 2, 8, 10, 5, 2, 7, 9, 3, 12, 2, 1, 3, 4, 7]…

        And we can show that these sequences repeat indefinitely, and as none of them contain 0, it demonstrates the two sequences have the required property.

        • Frits 8 October 2021 at 3:12 pm

          @Jim, instead of proving these sequences repeat indefinitely you might use (or add to enigma.py) a function which checks a list of numbers on repeating sequences (and with a minimum number of such sequences to occur before True is returned).

  2. Frits 8 October 2021 at 5:44 pm

    Function repseq is not totally accurate for certain odd m’s (example: if input contains 11 repetitions and m is set to 11 False is returned)

      
    from enigma import SubstitutedExpression
    
    # check the first <n> numbers of <s> and see if a sequence repeats itself
    def repseq(s, n=1000, m=1):
      if not type(s) is tuple:
        s = tuple(s) 
      rep = dict()
      n = min(n, len(s))
      i = 2
      while i < n:
        fh = s[:i//2]
        sh = s[i//2:i]
        # both halves same?
        if fh == sh:
          for k, v in rep.items():
            r = len(fh) // len(k)
            # sequence repeats itself <r> times?
            if k * r == fh:
              rep[k] = r * 2
              break
          else: # no break    
            # new sequence which repeats itself?
            if fh not in rep:
              rep[fh] = 2
        i += 2
        
      # check if sequence repeats itself at least <m> times
      for k, v in rep.items():
        if v < m: return dict()
          
      return rep
    
    # the alphametic puzzle
    p = SubstitutedExpression(
      [ # (b – a), (a), (b), (a + b), ..   with b = 3, 3 - a < 0 and a + b < 100  
        # 3 - a, a, 3, a + 3 with 4 <= a <= 96
       "4 <= AB <= 96",
       "not any(x % j == 0 for x in [3 - AB, AB, AB + 3] for j in [5, 11, 13])",
      ],
      answer="AB, (3 - AB, AB, 3, AB + 3)",
      verbose=0,
      d2i="",
      reorder=0,
    )
     
    # print answer
    firstnum = 1000
    for (_, ans) in p.solve():
      # check if candidate answers have repeated modulo sequences
      for d in (5, 11, 13):
        li = ans[1][:2]  
        cum = [x % d for x in li]
        # first <firstnum> entries
        for _ in range(firstnum - 2):
          new = li[-1] + li[-2]
          if new % d == 0: break
    
          li = [li[-1], new]
          cum.append(new % d)
        else: # no break      
          # check the first <firstnum> numbers of cumulative modulos
          if not repseq(cum, firstnum, 10): break
          
          continue  # next d
        
        # break occurred in previous loop
        break
      else: # no break  
        print(f"{ans[1]}")
    
  3. Pingback: New Scientist Enigma 642 – Fibonacciesque | PuzzlingInPython

  4. Jim Randell 9 October 2021 at 9:39 am

    Here is a program that examines each possible sequence and reports those that have no terms divisible by 5, 11, or 13.

    If we consider one of the sequences, each term is the sum of the previous two terms.

    So looking at the “mod sequence”, where each term is taken modulo k, we see that each term is also the sum (mod k) of the previous two terms.

    So, if we see two adjacent terms that we have seen before, we know the sequence must repeat.

    And there are only a finite number of pairs (mod k), so every mod sequence must eventually repeat.

    So we can look for zeros in the mod sequence, until we come across a pair of values we have seen before, and then we know for sure that there are no zeros in the entire sequence, and hence no terms divisible by k in the parent sequence.

    This Python program examines each sequence, and outputs those that with no terms divisible by 5, 11, or 13. It doesn’t need to know that there are exactly two sequences with this property. It runs in 55ms.

    Run: [ @replit ]

    from enigma import irange, fib, unpack, tuples, first, printf
    
    # make a mod sequence
    fibmod = lambda a, b, k: fib(a % k, b % k, fn=unpack(lambda x, y: (x + y) % k))
    
    # are there zeros in mod sequence s?
    def zero(s):
      # look for repeated pairs
      seen = set()
      for p in tuples(s, 2):
        if 0 in p: return True
        if p in seen: return False
        seen.add(p)
    
    # examine candidate sequences
    b = 3
    for a in irange(4, 96):
      # look for mod-sequences that contain no zeros
      if not any(zero(fibmod(b - a, a, k)) for k in (5, 11, 13)):
        printf("{ts} ...", ts=first(fib(b - a, a), 4))
    

    And it confirms that exactly 2 of the sequences have this property.

    We can use the same idea to show:

    (–28, 31, 3, …) has elements that are divisible by 17, but none that are divisible by 19.

    (–73, 76, 3, …) has no elements that are divisible by 17, but does have elements divisible by 19.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

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

%d bloggers like this: