# What are the repeating Fibonacci Digits?

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 , so the lowest number of bytes wins.

• Can we take 2 digits as input, instead of $0\le n \le 99$? Jan 9, 2019 at 17:47
• As in, take two inputs rather than one input that’s split? No. Jan 9, 2019 at 17:48
• I still don't understand why 14 and 59 give the same result. If 59 is interpreted as starting 5,9 and allowing that as part of the loop then surely 14 should be the start of its loop?
– Neil
Jan 9, 2019 at 21:23
• @williamporter The beginning of the sequence is 0,1,1,2,3,5,8,13,4,7,11,2,3. The first time that the loop repeats is at the second 2. Jan 9, 2019 at 21:24
• @Neil The beginning of those respective sequences is 1,4,5,9,14,5 and 5,9,14,5,9. Both of them repeat beginning with the second 5. As I said earlier, only the input is split up; later numbers keep their digits together in the sequence. Jan 9, 2019 at 21:25

# 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].


# 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


# 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


# Python 3, 1871761581391381291211201129695120 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
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]

• Small correction: this is Python 3.6+. This will plainly not work in 3.5 or older.
– 0xdd
Jan 9, 2019 at 21:49
• Your testing code seems to not work; an input of 59 yields (14, 5, 9)
– ArBo
Jan 11, 2019 at 23:38
• I see that test cases have changed since I began the challenge so that's why there was incorrect output. I've changed my solution so that it works but for now it's not so short. Nevertheless thanks for pointing that out. Jan 12, 2019 at 10:25

# C (gcc), 114112 109 bytes

f(n,s){int i={};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={};                               //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
}

• huh, do...while doesn't need the braces if it's a single statement O_o Jan 12, 2019 at 8:47

# Perl 5, 90 76 bytes

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


TIO

• @JoKing, fixed and optimized Jan 10, 2019 at 13:38

# 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!

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


# Python 2, 123114 113 bytes

n=input()
p=b=l=n/10,n%10
while~-(b in p):p+=b,;l+=(b/10or b%10)+b%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.

# 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.

# Red, 189178164 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!

# 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]


# 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

• Ṡ-U_2 is an interesting function. Nov 15, 2020 at 16:18