Generate the nth Narayana-Zidek-Capell number given an input n. Fewest bytes win.
f(1)=1, f(n) is the sum of the previous floor(n/2) Narayana-Zidek-Capell terms.
f(1)=1 f(9)=42 f(14)=1308 f(15)=2605 f(23)=664299
Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.Sign up to join this community
This uses a formula from the OEIS page for the Narayana-Zidek-Cappell numbers.
Edit: Got rid of parentheses using operator precedence with thanks to feersum and Neil.
n as argument and prints the result.
H divide input by 2 Ċ round up to get first n to recurse r inclusive range from that to n µ (chain separator) Ṗ remove n itself from the range ß€ call self recursively on each value in the range S sum results ȯ1 if sum was zero, return one
Algorithm taken from the OEIS page.
n<3 may be changed to
n<4 with no effect. Returns the
nth number, where
n is a positive integer.
a=lambda n:n<3or 2*a(n-1)-n%2*a(n/2)
An iterative solution as 05AB1E doesn't have functions.
X¸sGDN>;ï£Os‚˜}¬ X¸ # initialize a list with 1 sG } # input-1 number of times do D # duplicate current list N>;ï£ # take n/2 elements from the list O # sum those elements s‚˜ # add at the start of the list ¬ # get the first element and implicitly print
def f(n): x=1, for i in range(n):x+=sum(x[-i//2:]), print(x[-1])
A function that takes input via argument and prints to STDOUT. This is a direct implementation of the definition.
How it works
def f(n): Function with input target term index n x=1, Initialise term list x as tuple (1) for i in range(n):... For all term indices in [0,n-1]... x[-i//2:] ..yield the previous floor(i/2) terms... x+=sum(...) ...and append their sum to x print(x[-1]) Print the last term in x, which is the nth term
This is a full program without recursion. A recursive function can be defined in 52 bytes (it might be possible to beat that) but that's just a pretty boring port of sherlock9's answer (and it errors if you ask for f(100) or more) so I'm putting up this longer and more interesting version
Causes many (O[n]) notices but that's fine.
Based on the C answer.