A fountain is arrangement of coins in rows so that each coin touches two coins in the row below it, or is in the bottom row, and the bottom row is connected. Here's a 21 coin fountain:
Your challenge is to count how many different fountains can be made with a given number of coins.
You will be given as input a positive integer
n. You must output the number of different
n-coin fountains that exist.
Standard I/O rules, standard loopholes banned. Solutions should be able to calculate
n = 10 in under a minute.
Desired output for
n = 1 ... 10:
1, 1, 2, 3, 5, 9, 15, 26, 45, 78
This sequence is OEIS A005169.
This is code golf. Fewest bytes wins.
nfor which the program must be guaranteed to work? (i.e. after which it may break) \$\endgroup\$
n, up to limitations of datatype, hardware, etc. \$\endgroup\$