Inverse n-bonacci sequence

Question

We all know about the Fibonacci sequence. We start with two 1s and keep getting the next element with the sum of previous two elements.

n-bonacci sequence can be defined in similar way, we start with n 1s and take the sum of previous n elements to get the next element.

Challenge

Given a positive integer m > 1, output the smallest n of the n-bonacci sequence that contains m, and the index of m in that sequence (either 0 or 1 indexed).

There should be two integers in output, one will be which n-bonacci sequence the number is in, and another for the 0 or 1-indexed index in it.

I/O is flexible, you may choose to output either list, string or two numbers with optional trailing whitespace.

Test cases

First integer is which n-bonacci sequence and second is 0-indexed position:

2 -> 2,2
3 -> 2,3
4 -> 4,4
5 -> 2,4
6 -> 6,6
7 -> 4,5
8 -> 2,5
9 -> 3,5
10 -> 10,10
11 -> 6,7
12 -> 12,12
13 -> 2,6
14 -> 14,14
15 -> 8,9
16 -> 16,16
17 -> 3,6
18 -> 18,18
19 -> 10,11
20 -> 20,20
21 -> 2,7
22 -> 22,22
23 -> 12,13
24 -> 24,24
25 -> 4,7
26 -> 26,26
27 -> 14,15
28 -> 28,28
29 -> 8,10
30 -> 30,30
31 -> 3,7
32 -> 32,32
33 -> 5,8
34 -> 2,8
35 -> 18,19
36 -> 36,36
37 -> 10,12
38 -> 38,38
39 -> 20,21
40 -> 40,40
41 -> 6,9
42 -> 42,42
43 -> 22,23
44 -> 44,44
45 -> 12,14
46 -> 46,46
47 -> 24,25
48 -> 48,48
49 -> 4,8
50 -> 50,50
51 -> 26,27
52 -> 52,52
53 -> 14,16
54 -> 54,54
55 -> 2,9
56 -> 56,56
57 -> 3,8
58 -> 58,58
59 -> 30,31
60 -> 60,60
61 -> 16,18
62 -> 62,62
63 -> 32,33
64 -> 64,64
65 -> 5,9
66 -> 66,66
67 -> 34,35
68 -> 68,68
69 -> 18,20

This is code-golf so shortest answer wins.

Answer 1

05AB1E, 17 bytes

Lã.ΔR`©Å1λè®L₆O}Q

Try it online! or Try all cases!

L                   # range from 1 to the input
 ã                  # all pairs [n,k] where n and k are from the range
                    # this is sorted by the first element
  .Δ                # find the first such pair which satisfies:
    R`              #   reverse and splat, such that n is above k on the stack
      ©             #   store n in the register
       Å1           #   a list of n 1's as a start for the n-bonacci sequence
         λè    }    #   get the kth element of the recursively defined sequence
           ®L       #     push the range [1..n]
             ₆      #     for each of those numbers i, get the ith previous value
              O     #     sum those values
                Q   #   is this equal to the input

Answer 2

Jelly, 12 bytes

b©1ḋ®;Ɗ¡)Uœi

Try it online!

Multidimensional first index rocks again. Outputs (which n-bonacci sequence, 1-based index in it).

How it works

b©1ḋ®;Ɗ¡)Uœi    Full program; Input = n, the number to search for
        )       For each of i=1..n,
b©1ḋ®;Ɗ¡        Generate i-bonacci sequence up to n+i terms:
b©1               i copies of 1; save it to register
       ¡          Repeat n times:
   ḋ®;Ɗ             Prepend the sum of first 3 terms to the current list
         U      Reverse each list
          œi    Find the multi-dimensional index of the first occurrence of n

Answer 3

Wolfram Language (Mathematica), 64 bytes

LinearRecurrence[o=1~Table~n,o,#+1]~Table~{n,#}~FirstPosition~#&

Try it online!

Answer 4

Charcoal, 50 42 bytes

Ｎθ≔Ｅ⊕θＥι¹ηＦθＵＭη∧κ⊞ＯκΣ…⮌κλ≔§Φη№ιθ⁰ζＩ⟦⌕ηζ⌕ζθ

Try it online! Link is to verbose version of code. Edit: Saved 8 bytes by using @Bubbler's idea of calculating the first n+i elements of each i-bonacci series. Explanation:

Ｎθ

Input n.

≔Ｅ⊕θＥι¹η

Create a list of n+1 lists of 1s.

Ｆθ

Repeat n times...

ＵＭη∧κ⊞ＯκΣ…⮌κλ

... append the sum of the latest k terms to each list.

≔§Φη№ιθ⁰ζ

Find the first list which contains n.

Ｉ⟦⌕ηζ⌕ζθ

Output its index and the index of n in the list.

Answer 5

JavaScript (V8), 105 bytes

a=>{for(i=1;i++;)for(j=Array(i).fill(1);(k=eval(j.slice(-i).join`+`))<=a;h=j.push(k))if(k==a)return[i,h]}

Try it online!

Explanation

a => {                            // Defining a function that takes a single argument
  for (i = 1; i++; )              // With the variable i (sequence #) infinitely increasing
    for (                         // Iterate...
      j = Array(i).fill(1);       // Initialise j to array of 1s
      (k =                        // Assigning k to...
        eval(j.slice(-i).join`+`) // Sum of last i elements of j
      ) <= a;                     // Continue with this as long as we haven't passed a number greater than the input
      h = j.push(k)               // Push k to j, and assign h to index in sequence
    ) if( k == a)return[i,h]      // If we've found it, return
}

Answer 6

Wolfram Language (Mathematica), 82 bytes

returns 1-indexed

(k=2;While[(l=LinearRecurrence[s=1~Table~k,s,#+1])~FreeQ~#,k++];{k,l~Position~#})&

Try it online!

Answer 7

Python 3, 105 bytes

f=lambda n,b=2,p=1,l=[1,1]:l[-1]==n and(b,p)or f(*[n]+[[b,p+1,l+[sum(l[-b:])]],[b+1,b,[1]*-~b]][l[-1]>n])

Try it online!

may reach recursion limit, 0-indexed

Explanation

Simple recursive search algorithm

• f is the recursive function which takes an integer n

• Three variables are defined at start

  • b is the current number of n-bonacci sequence we are trying, which is initially Fibonacci aka 2

  • p is the 0-indexed position of current value we are trying which is also set to 1

  • l is the list from which will contain the b-bonacci numbers, which is for Fibonacci is [1,1]

• If the tail/last element of l is equal to n (tail of l is the last computed b-bonacci number)

  • We found our element so we return b and p

• Else

  • (We hold the possible values for the new recursive call as 2 lists in a list and index them with condition, get it and unpack on f to make recursive call)

  • If the tail of l is greater than n

    • Which means we have exceeded the limit and n is not in the current b-bonacci sequence, so

    • Make a recursive call with

      • n without any changes

      • b incremented by 1 to get to the next b-bonacci sequence

      • p as the old value of b because the search skips the 1s at the beginning so we need to offset by b

      • l as list of one more 1s (b minus 1 times)

  • If less than

    • We need to continue the search in current b-bonacci sequence

    • Make a recursive call with

      • n without any changes

      • b without any changes to continue the search

      • p increment by 1 to get to new index

      • Take b values from the tail of old l with negative indexing, sum them and append to old l to pass as new l

Answer 8

Lua's a terrible language for code-golfing by any standard, but it was still a ton of fun.

Lua, 250 bytes

T=table.unpack function S(t,a)return#t==0 and a or S({T(t,2,#t)},a+t[1])end function f(n,s)a={}for c=1,s do a[c]=1 end::B::l=S({T(a,#a-s+1,#a)},0)if l==n then return s,#a end a[#a+1]=l if l<n then goto B end return f(n,s+1) endprint(f(io.read"*n",2))

Lua, 280 bytes

function S(t,a)if #t==0 then return a end return S({table.unpack(t,2,#t)},a+t[1]) end function f(n,s)a={} for c=1,s do a[c]=1 end ::B:: l = S({table.unpack(a,(#a-s)+1,#a)},0)if l==n then return s,#a end a[#a+1]=l if l<n then goto B end return f(n,s+1)end print(f(io.read("*n"),2))

Answer 9

JavaScript (Node.js), 77 bytes

m=>(h=i=>(g=(i,k=n)=>i<k||k&&g(--i)+g(i,k-1))(i)-m?h(i<m?++i:++n):[n,i])(n=2)

Try it online!

Very slow but a bit shorter.

---

JavaScript (Node.js), 79 bytes

m=>(h=i=>(g=(i,k=n)=>t=i<k||k&&g(--i)+g(i,k-1))(i)-m?h(t<m?++i:++n):[n,i])(n=2)

Try it online!

A bit faster...

Answer 10

Ruby, 81 74 bytes

g=->x,y=2{s,n=[1]*y,0
s<<n=s[-y,y].sum while x>n
x<n ?g[x,y+1]:[y,s.size]}

Try it online!

• Saved 7Bytes thanks to @Dingus suggestions
• 1 indexed

g=-> x,y=2{  # recursive lambda testing each y-fib
               returning the first valid result
s,n=[1]*y,0  # s = current serie initialized to 1's
               n = next term

while x> n   # add terms up to x
=s[-y..-1].sum # which is sum of last y terms
s<<n end     # add it
x==n ?       # if last term is x
[y,s.size]   # return y and length 
:g[x,y+1]}   # else try next y-fib

Answer 11

C (gcc), ¹³⁹ 130 bytes

t;*b;j;s;i;*f(n){b=calloc(n,8);for(t=*b=s=1;t;)for(b[i=s++]=1;t&&n/++i;t=b[i]-n)for(b[j=i]=0;j-->i-s;)b[i]+=b[j];*b++=s;*b=i;--b;}

Try it online!

Inputs integer \$n>1\$.
Returns a pointer to an array \$a\$ where \$a[0]=s\$ (the sequence number) and \$a[1]=i\$ (the \$0\$-based index) of the first occurrence of \$n\$ in an \$n\$-bonacci sequence.

Answer 12

JavaScript (ES6), 84 bytes

f=(n,i=k=2)=>(g=(i,h=j=>j&&g(--i)+h(j-1))=>v=i<k||h(k))(i)-n?f(n,v<n?i+1:!k++):[k,i]

Try it online!

Answer 13

APL (Dyalog Classic), 62 bytes

{l←1+⍵⋄⊃(,∘.,⍨⍳l)/⍨⍵=,1⌽↑l{⍺{d←⍵⋄({⍵,+/⍵↑⍨-d}⍣(⍺-⍵))d⍴1}¨⍵}⍳l}

Try it online!

Answer 14

R, 92 bytes

function(m)while(F<-F+1)for(i in 0:m+1)if((T[i]=`if`(i>F,sum(T[i-1:F]),1))==m)return(c(F,i))

Try it online!

Returns 1-based indices.