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

• Arnauld: Can we take 2 digits as input, instead of \0ドル\le n \le 99\$?
• DonielF: As in, take two inputs rather than one input that’s split? No.
• Neil: 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?
• DonielF: @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.
• DonielF: @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.

Answer 1

Jelly, 15 bytes

DFṫ-SṭḊ
d5ÇÐḶZḢ

Try it online!

How it works

d5ÇÐḶZḢ Main link. Argument: n (integer)
d5 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]

• 0xdd: Small correction: this is Python 3.6+. This will plainly not work in 3.5 or older.
• ArBo: Your testing code seems to not work; an input of 59 yields (14, 5, 9)
• Nishioka: 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.

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
}

• ASCII-only: huh, do...while doesn't need the braces if it's a single statement O_o

Answer 6

Perl 5, (削除) 90 (削除ここまで) 76 bytes

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

TIO

• Nahuel Fouilleul: @JoKing, fixed and optimized

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

≔E◧S2ΣιθW¬υ≔ΦE⊖L⊞OθΣ...⮌⪫θω2✂θλLθ1=κ✂θ⊗−λLθλ1υIυ

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

≔E◧S2Σιθ

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

W¬υ

Repeat while the list of loops is empty.

⊞OθΣ...⮌⪫θω2

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

E⊖L...✂θλLθ1

Take all the nontrivial suffixes of the list.

≔Φ...=κ✂θ⊗−λLθλ1υ

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

Iυ

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

• Razetime: Ṡ-U_2 is an interesting function.