Inverse n-bonacci sequence

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 so shortest answer wins.

• Welcome to Code Golf! This looks like a reasonably well-specified challenge, but in future we highly recommend using the Sandbox to get feedback on your questions before posting them to main. Oct 26, 2021 at 8:35
• May we output the integers in reversed order (first being the indexed position, second being the th n-bonacci sequence)? Oct 26, 2021 at 9:37
• @KevinCruijssen yes you can Oct 26, 2021 at 9:46
• What do you exactly mean with first occurrence? The lowest n-bonacci sequence it appears in or the lowest index it has in any n-bonacci?
– ovs
Oct 26, 2021 at 10:39
• @Noodle I haven't found an example (searched to ~90000) and there might be none, but I think that this is not necessarily the same. Hypothetical example: $100$ appears in 2-bonacci at index $10$ but at index $9$ in 3-bonacci (3-bonacci > 2-bonacci starting at index 6)
– ovs
Oct 26, 2021 at 11:04

05AB1E, 17 bytes

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

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

• Nice answer! I've just asked OP if the outputs can be in reversed order, in which case it would save the R. And unfortunately it doesn't save bytes, but the ©Å1 and ®L could alternatively be Å1© and ®ƶ, which I thought was a funny coincidence. Oct 26, 2021 at 9:41
• OP just said you can output them in reverse order, so you can remove the R for -1 (unless you know an edge case for which this doesn't apply, considering the .Δ returns the first pair; it does work for all test cases in your test suite however). Oct 26, 2021 at 9:50
• @KevinCruijssen I'm not sure about that one. A few other answer already seem to use that the lowest n-bonacci that contains the input will be the earliest occurence, but I can't see why that would be the case
– ovs
Oct 26, 2021 at 10:31

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


Wolfram Language (Mathematica), 64 bytes

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


Try it online!

• you were 1 min faster and of course some bytes shorter ;) nice! Oct 26, 2021 at 9:31

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.

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
}


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!

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

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

• Welcome to Code Golf, and nice first answer! Make sure to check out our tips for golfing in Lua to see if there are any ways for you to shorten your code. Oct 26, 2021 at 16:16
• thanks, that reminded me of the ternary operator. Oct 26, 2021 at 17:10

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

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

• You can avoid end by using the modifier form of while. [-y..-1] can be [-y,y] and you can save another byte on the ternary conditional by testing for x<n instead and swapping the branches. Oct 26, 2021 at 23:04

C (gcc), 139 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.

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!

APL (Dyalog Classic), 62 bytes

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


Try it online!

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.