Enigmatic Code

Programming Enigma Puzzles

Enigma 979: Triangular and Fibonacci numbers

From New Scientist #2134, 16th May 1998 [link]

Triangular numbers are those that fit the formula n(n + 1)/2, so that the sequence starts: 1, 3, 6, 10, 15, 21, 28, …

From the first 30 triangular numbers select a set that uses each of the ten digits 0 to 9 once.

1. What are the largest and smallest numbers in your set?

In the Fibonacci sequences the first two terms are 1 and 1 and each succeeding term is the sum of the previous two terms, so that sequence starts: 1, 1, 2, 3, 5, 8, 13, …

From the first 30 Fibonacci numbers select a set that uses each of the ten digits 0 to 9 once.

2. What are the largest and smallest numbers in your set?

[enigma979]

One response to “Enigma 979: Triangular and Fibonacci numbers

  1. Jim Randell 20 December 2019 at 9:14 am

    I am assuming we want the sets to use each digit exactly once (otherwise the entire sets of 30 numbers would do).

    This Python 3 program runs in 91ms.

    Run: [ @repl.it ]

    from enigma import first, T, irange, fib, filter2, is_duplicate, join, printf
    
    # find subsets of <ss> that use each digit exactly once
    # elements of <ss> should not contain repeated digits
    def solve(ss, s=[], ds=set()):
      # are all digits used?
      if len(ds) == 10:
        yield s
      elif ss:
        # can we add in the next element?
        x = ss[0]
        if not(ds.intersection(x)):
          yield from solve(ss[1:], s + [ss[0]], ds.union(x))
        # try without it
        yield from solve(ss[1:], s, ds)
    
    
    # first 30 triangular numbers
    tris = map(T, irange(1, 30))
    
    # first 30 fibonacci numbers
    fibs = first(fib(1, 1), count=30)
    
    # find solutions
    for (i, ss) in enumerate([tris, fibs], start=1):
      # select numbers with no repeated digits (as strings)
      (_, ss) = filter2(is_duplicate, map(str, ss))
      # find pandigital subsets
      for s in solve(ss):
        printf("[{i}] {s}", s=join(s, sep=", "))
    

    Solution: (1) The largest number is 406. The smallest number is 78. (2) The largest number is 987. The smallest number is 2.

    There are two possible sets for part (1):

    78, 91, 253, 406
    78, 91, 325, 406

    But only one set for part (2):

    2, 5, 34, 610, 987

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: