What are the repeating Fibonacci Digits?

Question

As you probably know, a Fibonacci Number is one which is the sum of the previous two numbers in the series.

A Fibonacci Digit™ is one which is the sum of the two previous digits.

For instance, for the series beginning 1,1, the series would be 1,1,2,3,5,8,13,4,7,11,2... The change occurs after the 13, where, instead of adding 8+13, you add 1+3. The series loops at the end, where 4+7=11, and 1+1=2, same as the series starts.

For another example, the series beginning 2,2: 2,2,4,6,10,1,1,2,3,5,8,13,4,7,11,2,3.... This one starts out uniquely, but once the digits sum to 10, you end up with 1+0=1, 0+1=1, and the series continues - and loops - the same way the 1,1 series did.

---

The Challenge

Given an integer input 0≤n≤99, calculate the loop in the Fibonacci Digit series beginning with those two digits. (You are certainly allowed to consider integers out of this range, but it's not required.) If given a one-digit input, your code should interpret it to denote the series beginning 0,n.

All numbers in the loop that are two-digits must be outputted as two digits. So, for instance, the loop for 1,1 would contain 13, not 1,3.

The output begins with the first number in the loop. So, based on the above restrictions, the loop for 1,1 begins with 2, since 1,1 and 11 are counted separately.

Each number of the output may be separated by whatever you want, as long as it's consistent. In all of my examples I use commas, but spaces, line breaks, random letters, etc. are all allowed, as long as you always use the same separation. So 2g3g5g8g13g4g7g11 is a legal output for 1, but 2j3g5i8s13m4g7sk11 is not. You can use strings, lists, arrays, whatever, provided that you have the correct numbers in the correct order separated by a consistent separator. Bracketing the entire output is also allowed (ex. (5,9,14) or [5,9,14], etc.).

Test Cases:

1 -> 2,3,5,8,13,4,7,11
2 -> 2,3,5,8,13,4,7,11
3 -> 11,2,3,5,8,13,4,7
4 -> 3,5,8,13,4,7,11,2
5 -> 2,3,5,8,13,4,7,11
6 -> 3,5,8,13,4,7,11,2
7 -> 14,5,9
8 -> 13,4,7,11,2,3,5,8
9 -> 11,2,3,5,8,13,4,7
0 -> 0
14 -> 5,9,14
59 -> 5,9,14

This is code-golf, so the lowest number of bytes wins.

Answer 1

Jelly, 15 bytes

DFṫ-SṭḊ
d⁵ÇÐḶZḢ

Try it online!

How it works

d⁵ÇÐḶZḢ  Main link. Argument: n (integer)

d⁵       Divmod 10; yield [n:10, n%10].
  ÇÐḶ    Call the helper link until a loop is reached. Return the loop.
     Z   Zip/transpose the resulting array of pairs.
      Ḣ  Head; extract the first row.


DFṫ-SṭḊ  Helper link. Argument: [a, b] (integer pair)

D        Decimal; replace a and b with the digits in base 10.
 F       Flatten the resulting array of digit arrays.
  ṫ-     Tail -1; take the last two digits.
    S    Compute their sum.
      Ḋ  Dequeue; yield [b].
     ṭ   Append the sum to [b].

Answer 2

Perl 6, 96 78 75 bytes

-3 bytes thanks to nwellnhof

{0,|.comb,((*~*)%100).comb.sum...{my$a=.tail(2);m/(\s$a.*)$a/}o{@_};$_&&$0}

Try it online!

0 returns 0, and other number return a Match object which stringifies to the numbers separated by a space with a leading a trailing space.

Explanation:

{                                                                         }   # Anonymous code block
 0,|.comb,                    ...   # Start a sequence with 0,input
                                    # Where each element is
                          .sum      # The sum of
          (     %100).comb          # The last two digits
           (*~*)                    # Of the previous two elements joined together
                                                                         # Until
                                 {                           }o{@_}   # Pass the list into another function
                                  my$a=.tail(2); # Save the last two elements
                                                m/(\s$a.*)$a/  # The list contains these elements twice?
                                                                     # And return
                                                                   ;$_     # Input if input is 0
                                                                      &&   # Else
                                                                        $0 # The looping part, as matched

Answer 3

JavaScript (ES6),  111 104  103 bytes

f=(n,o=[p=n/10|0,n%10])=>n^o[i=o.lastIndexOf(n=(q=p+[p=n])/10%10+q%10|0)-1]?f(n,[...o,n]):o.slice(i,-1)

Try it online!

Commented

f = (                       // f = recursive function taking:
  n,                        //    n = last term, initialized to the input
  o = [                     //    o = sequence, initially containing:
    p = n / 10 | 0,         //      p = previous term, initialized to floor(n / 10)
    n % 10 ]                //      n mod 10
) =>                        //
  n ^                       // we compare n against
  o[                        // the element in o[] located at
    i = o.lastIndexOf(      //   the index i defined as the last position of
      n =                   //     the next term:
        (q = p + [p = n])   //       q = concatenation of p and n; update p to n
        / 10 % 10           //       compute the sum of the last two digits
        + q % 10            //       of the resulting string
        | 0                 //       and coerce it back to an integer
      ) - 1                 //   minus 1
  ] ?                       // if o[i] is not equal to n:
    f(n, [...o, n])         //   append n to o[] and do a recursive call
  :                         // else:
    o.slice(i, -1)          //   we've found the cycle: return it

Answer 4

Python 3, 187 176 158 139 138 129 121 120 112 96 95 120 116 bytes

f=lambda n,m=0,z=[]:(n,m)in zip(z,z[1:])and z[z.index(m)::-1]or f((z and n//10or m%10)+n%10,z and n or n//10,(m,*z))

Try it online!

Edit: As noted by @Jules, shorter solution applies to Python 3.6+. No longer distinct solutions for Python 3 / 3.6+

Edit: Indexing of z was too verbose. Without that now there is no gain in using eval.

Edit: Simplified finding if last two elements already appeared in the sequence.

Edit: Changed output format from list to tuple + replaced lambda with def

Edit: Back to lambda but embedded t into f.

Edit: Input n can be actually interpreted as head of growing collection z which would represent tail in recursive approach. Also beats @Arbo's solution again.

Edit: Actually you can unpack two items from head which cuts another 16 bytes.

Edit: Actually 17 bytes.

Edit: As noted by @Arbo solution was giving answers for 14 and 59 cases as they were in initial test cases which were proven later to be wrong. For now this isn't so short but at least it works correctly.

---

Quite an abuse of f-strings and eval. Original ungolfed code although I suspect it could be done somehow easier:

def is_subsequence(l1, l2):
    N, n = len(l1), len(l2)
    for i in range(N-n):
        if l1[i:i+n]==l2:
            return True
    return False

def generate_sequence(r):
    if is_subsequence(r,r[-2:]):
        return r
    last_two_digits = "".join(map(str,r))[-2:]
    new_item = sum(int(digit) for digit in last_two_digits)
    return generate_sequence(r + [new_item])

def f(n):
    seq = generate_sequence([n,n])[::-1]
    second_to_last = seq[1]
    first_occurence = seq.index(second_to_last)
    second_occurence = seq.index(second_to_last, first_occurence + 1)
    return seq[first_occurence + 1 : second_occurence + 1][::-1]

Answer 5

C (gcc), 114 112 109 bytes

f(n,s){int i[19]={};for(s=n/10,n%=10;i[s]-n;n+=n>9?-9:s%10,s=i[s])i[s]=n;for(;printf("%d ",s),i[s=i[s]]-n;);}

Try it online!

-3 from ceilingcat

Includes a trailing space.

f(n,s){
    int i[19]={};                               //re-initialize edges for each call
    for(s=n/10,n%=10;                           //initialize from input
        i[s]-n;                                 //detect loop when an edge s->n repeats
        n+=n>9?-9:s%10,s=i[s])i[s]=n;           //step
    for(;printf("%d ",s),i[s=i[s]]-n;);         //output loop
}

Answer 6

Perl 5, 90 76 bytes

s/.\K/ /;s/(.?) *(.)\K$/$".($1+$2)/e until/^0|\b(.\B.|. .)\b.*(?= \1)/;$_=$&

TIO

Answer 7

Java (JDK), 194 bytes

n->"acdfinehlcdfinehfjofj".chars().map(x->x-97).skip((n="abbicbcsfibbbgqifiibbgbbbcsfbiiqcigcibiccisbcqbgcfbffifbicdqcibcbicfsisiibicfsiffbbicfsifiibicfsifii".charAt(n)%97)).limit(n<1?1:n<9?8:3)

Try it online!

Hardcoded seemed the shortest given that Python already had an answer of 187...

Answer 8

Haskell, 100 bytes

d!p@(s,t)|(_,i:h)<-span(/=p)d=fst<$>i:h|q<-d++[p]=q!(t,last$mod s 10+t:[t-9|t>9])
h x=[]!divMod x 10

Try it online!

d!p@(s,t)                -- function '!' recursively calculates the sequence
                         -- input parameter:
                         -- 'p': pair (s,t) of the last two numbers of the sequence
                         -- 'd': a list of all such pairs 'p' seen before
  |       <-span(/=p)d   -- split list 'd' into two lists, just before the first
                         -- element that is equal to 'p'
   (_,i:h)               -- if the 2nd part is not empty, i.e. 'p' has been seen
                         -- before
          =fst<$>i:h     -- return all first elements of that 2nd part. This is
                         -- the result.
  |q<-d++[p]             -- else (p has not been seen) bind 'q' to 'd' followed by 'p'
   =q!                   -- and make a recursive call to '!' with 'q' and
     (t,    )            -- make the last element 't' the second to last element
                         -- the new last element is
          [t-9|t>9]      -- 't'-9 (digit sum of 't'), if 't'>9
       mod s 10+t        -- last digit of 's' plus 't', otherwise

h x=                     -- main function
     []!divMod x 10      -- call '!' with and empty list for 'd' and
                         -- (x/10,x%10) as the pair of last numbers

Answer 9

Python 2, 123 114 113 bytes

n=input()
p=b=l=n/10,n%10
while~-(b in p):p+=b,;l+=(b[1]/10or b[0]%10)+b[1]%10,;b=l[-2:]
print l[p.index(b)-2:-2]

Try it online!

The program builds up a tuple p of all 2-value pairs that have occurred in the sequence, which is initialised with junk to save some bytes. The sequence itself gets built in the tuple l, and the last two elements of this tuple are stored in b for easy (and short) reference. As soon as a repeat is found, we can look up the index of b in p to know where the loop began.

EDIT: Cleaned this up a bit, and shaved off one more byte... My method does seem to be nearing its byte count limit, and I really should stop working on this.

Answer 10

Charcoal, 46 bytes

≔Ｅ◧Ｓ²ΣιθＷ¬υ≔ΦＥ⊖Ｌ⊞ＯθΣ…⮌⪫θω²✂θλＬθ¹⁼κ✂θ⊗⁻λＬθλ¹υＩυ

Try it online! Link is to verbose version of code. Explanation:

≔Ｅ◧Ｓ²Σιθ

Input the number, pad it to 2 characters, then take the digital sum of each character, and save the resulting list.

Ｗ¬υ

Repeat while the list of loops is empty.

⊞ＯθΣ…⮌⪫θω²

Calculate the sum of the two previous digits and add it to the Fibonacci list.

Ｅ⊖Ｌ...✂θλＬθ¹

Take all the nontrivial suffixes of the list.

≔Φ...⁼κ✂θ⊗⁻λＬθλ¹υ

Filter out those that don't repeat and save the result in the list of loops.

Ｉυ

Cast the list of loops to string and print.

Answer 11

Red, 189 178 164 137 bytes

func[n][b: n % 10 c: reduce[a: n / 10]until[append c e: b
b: a *(pick[0 1]b > 9)+(a: b % 10)+(b / 10)k: find c reduce[e b]]take/last k k]

Try it online!

Answer 12

Python 2, 149 139 bytes

s=input()
s=[s/10,s%10]
while zip(s,s[1:]).count((s[-2],s[-1]))<2:s+=[(s[-1]/10or s[-2]%10)+s[-1]%10]
print s[-s[::-1].index(s[-2],2)-1:-2]

Try it online!

Expects a non-negative integer as input. Smaller bytecount, but likely will no longer work for integers >99.

Explanation:

# get the input from STDIN
s=input()
# convert the input into two integers via a divmod operation
s=[s/10,s%10]
# count number of times the last two numbers appear in sequence in list.
# turn list into list of adjacent value pairs Ex: [1,1,2]->[(1,1),(1,2)]
      zip(s,s[1:])
                  # count number of times the last two items in list appear in entire list
                  .count((s[-2],s[-1]))
# if >1 matches, we have found a repeat.
while .................................<2:
        # the first digit of the last number, if it is >9
        # else the last digit of the second to last number
        (s[-1]/10or s[-2]%10)
                             # the last digit of the last number
                             +s[-1]%10
    # add the new item to the list
    s+=[..............................]
         # reverse the list, then find the second occurrence of the second to last item
         s[::-1].index(s[-2],2)
# get the section of the list from the second occurrence from the end, discard the final two items of the list
print s[-......................-1:-2]

Answer 13

Husk, 15 bytes

UṠ-U_2¡ȯΣ↑_2ṁd;

Try it online!

UṠ-U_2¡ȯΣ↑_2ṁd;
U                   # longest prefix of unique elements from sequence
 Ṡ-U_2              # (after removing longest prefix with 
                    # all unique sublists of length 2)
      ¡ȯΣ↑_2ṁd;     # fibonacci digit sequence:
      ¡             # repeatedly apply function to list
              ;     # (starting with list formed from input):
       ȯ            # combination of 3 functions - 
        Σ           # sum of
         ↑_2        # last 2 elements of
            ṁd      # digits of list