Give the fool's Fibonacci sequence

Question

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 sequence 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 code-golf so the goal is to minimize the size of your program as measured in bytes.

• bsoelch: You should mark every third value in bold
• Bubbler: 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.
• Wheat Wizard: @Bubbler Either case is fine. I updated the question.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

Charcoal, 44 bytes

×ばつ3λI⌈η

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

F2⊞υι

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

≔E2ιη

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

FN

Calculate \$ n \$ new terms.

×ばつ3λ

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

I⌈η

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:

×ばつ✂⮌υ2χ3⟦4¦1±2⟧I§υ±3

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

F3⊞υ2

Start with 3 2s.

FN

Generate n more terms.

×ばつ✂⮌υ2χ3⟦4¦1±2⟧

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

I§υ±3

Output the nth term.

Answer 5

Python, (削除) 96 (削除ここまで) (削除) 72 (削除ここまで) 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!

• xnor: 66 bytes with map

Answer 6

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)

Answer 7

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
 +2 # add 2

Answer 8

Haskell, 76 bytes

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!

Answer 9

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), (削除) 74 (削除ここまで) (削除) 69 (削除ここまで) (削除) 65 (削除ここまで) 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.