13
\$\begingroup\$

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.

\$\endgroup\$
3
  • 5
    \$\begingroup\$ You should mark every third value in bold \$\endgroup\$
    – bsoelch
    Aug 20, 2023 at 16:00
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – Bubbler
    Aug 21, 2023 at 0:00
  • \$\begingroup\$ @Bubbler Either case is fine. I updated the question. \$\endgroup\$
    – Wheat Wizard
    Aug 23, 2023 at 11:31

9 Answers 9

8
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 44 bytes

F²⊞υι≔E²ιηFN⊞η⁻⌈⊞OυΣ…⮌υ²↨¹E✂⮌η⁵Lη³×κ§υ׳λI⌈η

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

F²⊞υι

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

≔E²ιη

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

FN

Calculate \$ n \$ new terms.

⊞η⁻⌈⊞OυΣ…⮌υ²↨¹E✂⮌η⁵Lη³×κ§υ׳λ

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:

F³⊞υ²FN⊞υΣ×✂⮌υ²χ³⟦⁴¦¹±²⟧I§υ±³

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

F³⊞υ²

Start with 3 2s.

FN

Generate n more terms.

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

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

I§υ±³

Output the nth term.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.