30
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Can we take 2 digits as input, instead of \$0\le n \le 99\$? \$\endgroup\$ – Arnauld Jan 9 at 17:47
  • 1
    \$\begingroup\$ As in, take two inputs rather than one input that’s split? No. \$\endgroup\$ – DonielF Jan 9 at 17:48
  • \$\begingroup\$ 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? \$\endgroup\$ – Neil Jan 9 at 21:23
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – DonielF Jan 9 at 21:24
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – DonielF Jan 9 at 21:25

12 Answers 12

10
\$\begingroup\$

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].
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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]
\$\endgroup\$
  • 1
    \$\begingroup\$ Small correction: this is Python 3.6+. This will plainly not work in 3.5 or older. \$\endgroup\$ – Jules Jan 9 at 21:49
  • 1
    \$\begingroup\$ Your testing code seems to not work; an input of 59 yields (14, 5, 9) \$\endgroup\$ – ArBo Jan 11 at 23:38
  • \$\begingroup\$ 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. \$\endgroup\$ – Nishioka Jan 12 at 10:25
4
\$\begingroup\$

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
}
\$\endgroup\$
  • 1
    \$\begingroup\$ huh, do...while doesn't need the braces if it's a single statement O_o \$\endgroup\$ – ASCII-only Jan 12 at 8:47
  • \$\begingroup\$ @ceilingcat thanks! \$\endgroup\$ – attinat Jan 12 at 19:32
3
\$\begingroup\$

Perl 5, 90 76 bytes

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

TIO

\$\endgroup\$
  • \$\begingroup\$ @JoKing, fixed and optimized \$\endgroup\$ – Nahuel Fouilleul Jan 10 at 13:38
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 46 bytes

≔E◧S²ΣιθW¬υ≔ΦE⊖L⊞OθΣ…⮌⪫θω²✂θλLθ¹⁼κ✂θ⊗⁻λLθλ¹υIυ

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

≔E◧S²Σιθ

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θΣ…⮌⪫θω²

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

E⊖L...✂θλLθ¹

Take all the nontrivial suffixes of the list.

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

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.