# Give the fool's Fibonacci sequence

Recently I asked for tips on improving some code-golf of mine. The code was supposed to output every third value of the Fibonacci sequence starting with 2:

2,8,34,144,610,2584,10946,46368,196418,832040


However, I made a mistake in deriving my formula, and my code output a different sequence which is accurate for the first couple terms and then begins to diverge:

2,8,34,140,578,2384,9834,40564,167322,690184


My sequence is defined by:

$$f(0) = 0 \\$$ $$f(1) = 2 \\$$ $$f(n) =\displaystyle 2 + 3f(n-1) + 4f(n-2) + 2\sum_{0}^{n-3}f\\$$

or in terms of my original Haskell code:

z=zipWith(+)
g=z((*2)<$>0:0:g)$z(0:g)$(*2)<$>scanl(+)1g


Your task is to implement a of integers, which has my incorrect sequence as every third value. The other values can be whatever you want them to be, it simply must have the above sequence as every third value. The required subsequence can begin at the 0th, 1st, or 2nd index, and may begin with either 0 or 2 whichever you please.

This is so the goal is to minimize the size of your program as measured in bytes.

• You should mark every third value in bold Aug 20, 2023 at 16:00
• What should be the first value of the "every third value", 0 or 2? Asking because your listing and Haskell code start with 2 but the definition starts at 0. Aug 21, 2023 at 0:00
• @Bubbler Either case is fine. I updated the question. Aug 23, 2023 at 11:31

# K (ngn/k), 23 bytes

{-2/z,x,y}/[;0;2;8] -3!


Try it online!

Given n, returns the nth term (0-indexed) of the given sequence triplicated, i.e. 0, 0, 0, 2, 2, 2, 8, 8, 8, 34, 34, 34, .... To start with 2 instead, change 0;2;8 to 2;8;34 or replace the space with 1+ for +1 byte.

The OP's sequence can be simplified as follows:

\begin{aligned} a_n &= a_{n-1} + 2a_{n-2} + 2\sum_{k=0}^{n-1}a_k + 2 \\ a_{n-1} &= a_{n-2} + 2a_{n-3} + 2\sum_{k=0}^{n-2}a_k + 2 \\ a_n - a_{n-1} &= a_{n-1} + 2a_{n-2} - a_{n-2} - 2a_{n-3} + 2a_{n-1} \\ a_n &= 4a_{n-1} + a_{n-2} - 2a_{n-3} \end{aligned}

Now we want to find a sequence whose every third term satisfies the above, i.e. the original sequence satisfies

$$a_n = 4a_{n-3} + a_{n-6} - 2a_{n-9}$$

but it turns out that this recurrence is irreducible, at least in integers. So the code simply evaluates the "every third term" sequence at index floor(n/3).

# Python, 51 bytes

f=lambda n:n>3and 4*f(n-3)+f(n-6)-2*f(n-9)or(n>0)*2


Attempt This Online!

Test harness borrowed from @bsoelch.

### How?

Taking the difference f(n)-f(n-3) gets rid of the sum.

# sclin, 39 bytes

[0 2 8]"dup [2_1 4] * +/ +1dp"itr flat


Try it here! Outputs an infinite list:

$$0,2,8,2,8,34,8,34,140,34,140,578,140,578,2384,...$$

For testing purposes:

; 100tk >A
[0 2 8]"dup [2_1 4] * +/ +1dp"itr flat


## Explanation

Prettified code:

[0 2 8] ( dup [2_ 1 4] * +/ + 1dp ) itr flat


Based on a simplified variant of the original equation (first found by @loopy walt and @Bubbler):

$$f(n)=4f(n-1)+f(n-2)−2f(n-3)$$

• [0 2 8] (...) itr creates an infinite series of modifications starting from 0, 2, 8
• dup [2_1 4] * vectorized-multiply each term by -2, 1, 4
• +/ sum
• + 1dp append as new term, discard oldest term
• flat flatten, which conveniently also creates a 2-term gap

# Charcoal, 44 bytes

Ｆ²⊞υι≔Ｅ²ιηＦＮ⊞η⁻⌈⊞ＯυΣ…⮌υ²↨¹Ｅ✂⮌η⁵Ｌη³×κ§υ×³λＩ⌈η


Try it online! Link is to verbose version of code. Outputs $$\ f(n) \$$ where $$\ f(2)=2 \$$. Explanation:

Ｆ²⊞υι


Start with the first two terms of the Fibonacci sequence ($$\ 0 \$$-indexed).

≔Ｅ²ιη


Start with the first two terms of the Wheat Wizard sequence ($$\ 0 \$$-indexed).

ＦＮ


Calculate $$\ n \$$ new terms.

⊞η⁻⌈⊞ＯυΣ…⮌υ²↨¹Ｅ✂⮌η⁵Ｌη³×κ§υ×³λ


Calculate $$\ F(n) \$$ and $$\ f(n)=F(n)-\sum_{i=0}^{\lfloor(n-5)/3\rfloor}F(3i)f(n-5-3i) \$$.

Ｉ⌈η


Output the $$\ n \$$th additional term. This results in the following sequence:

$$1, 2, 3, 5, 8, 13, 21, 34, 53, 87, 140, 219, 359, 578, 903, 1481, 2384, 3725, 6109, 9834, 15365, 25199, 40564, 63379, 103943, 167322, 261431, 428753, 690184,$$

29 bytes for the boring version with all the values triplicated:

Ｆ³⊞υ²ＦＮ⊞υΣ×✂⮌υ²χ³⟦⁴¦¹±²⟧Ｉ§υ±³


Attempt This Online! Link is to verbose version of code. Outputs the first n terms. Explanation:

Ｆ³⊞υ²


Start with 3 2s.

ＦＮ


Generate n more terms.

⊞υΣ×✂⮌υ²χ³⟦⁴¦¹±²⟧


Calculate the next term using @loopywalt/@Bubbler's formula.

Ｉ§υ±³


Output the nth term.

# Python, 9672 66 bytes

-6 bytes, thanks to @xnor

f=lambda n:n>0and 2+3*f(n-3)+4*f(n-6)+2*sum(map(f,range(0,n-8,3)))


Attempt This Online!

# 05AB1E, 16 14 bytes

2λ‚āR*λ·«OÌ}€Ð


Outputs the infinite sequence starting with $$\2\$$, where all values occur three times in a row.

Try it online.

Explanation:

 λ          # Start a recursive environment,
# to output the infinite sequence
2           # Starting with a(0)=2
# Where every following a(n) is calculated as:
‚         #  Pair the last two implicit values together: [a(n-2),a(n-1)]
#  (uses a(n-2)=0 in the first iteration: [0,2])
āR       #  Push pair [2,1]
*      #  Multiply the values at the same positions: [2*a(n-2),a(n-1)]
λ     #  Push a list of all terms thus far: [a(0),a(1),...,a(n-1)]
·    #  Double each: [2*a(0),2*a(1),...,2*a(n-1)]
«   #  Append the lists together: [2*a(n-2),a(n-1),2*a(0),2*a(1),...,2*a(n-1)]
O  #  Take its sum
Ì #  And increase it by 2
}          # After the recursive sequence has been generated:
€Ð        # Triplicate each value in place
# (after which the infinite list is output implicitly as result)


# Pyth, 21 bytes

L&b+2su+@G1G3*2_%3yMb


Try it online!

Defines a function y, which when given N returns the Nth term in the sequence $$0, 2, 2, 2, 8, 8, 8, 34, 34, 34, 140, 140, 140, 578, 578, 578, 2384, 2384, 2384, \dots$$

### Explanation

L                        # define y(b)
&b                      # short circuiting and, if b==0: return 0
yMb    # map range(b) over y
%3       # take every third element
_         # reverse the list
*2          # and double it
u     3            # reduce range(3) over lambda G,H with the list as the starting value
+@G1G             #   add the second element of G to the beginning of G
s                   # sum


z=zipWith(+)
g=z((*2)<$>0:0:g)$z(0:g)$(*2)<$>scanl(+)1g
f=[x|x<-g,_<-[1..3]]


I don't really know Haskell that well, but I do enjoy loopholes. This is a direct ripoff of the code in the question, with each element repeated three times. Direct link for good measure.

Try it online!

# C (gcc), 62 bytes

b,c;main(a){for(a++;;)printf("0,0,%u,",a=-2*c+(c=b)+4*(b=a));}


Try it online!

New approach to a complete program, using the f(n)=4f(n-1)+f(n-2)-2f(n-3) formula used in other solutions.

It starts outputting the sequence at 8, not 0 or 2 as the challenge states.

I feel like this could be improved upon even further.

# C (gcc), 746965 63 bytes

a,b,t;main(c){for(;t=b+(c+=b);printf("0,0,%u,",a=3*a+2*t))b=a;}


Try it online!

After many reworks, this is what I came up with from following the same algorithm to its conclusion.

This implementation

• Depends on undefined behaviour (sequencing)
• Is a complete program, not a fragment.
• And computes the sequence explicitly, outputting zeros on all but every third number.

It may be shorter if we loop once per number output, instead of once every three numbers.