Implement the random Fibonacci sequence

Question

The random Fibonacci sequence is defined as follows:

$$ f_n = \begin{cases} f_{n-1}+f_{n-2} \text{ with probability } 1/2 \\ f_{n-1}-f_{n-2} \text{ with probability } 1/2 \\ \end{cases} $$ $$ f_1 = f_2 = 1 $$

i.e. whether the next term is the sum or difference of the previous two is chosen at random, independently of previous terms. Your task is to implement this sequence.

Each random realization of the sequence must use consistent values. For example, if \$f_3 = 2\$, \$f_4\$ must then be either \2ドル+1 = 3\$ or \2ドル-1 = 1\$. This can be thought of as the sequence "remembering" previous values. This means that this example program is invalid, as previous values in the sequence are not maintained by later values. Furthermore, you should explain how your program meets the \1ドル/2\$ probability requirement.

As is standard for sequence challenges, you can perform one of three tasks:

• Take a positive integer \$n\$ as input and output \$f_n\$
• Take a positive integer \$n\$ as input and output \$f_1, f_2, ..., f_n\$
• Output the sequence indefinitely with no end

Again, as is standard, you may use either \0ドル\$ or \1ドル\$ indexing, but the two initial values \$f_1 = f_2 = 1\$ must be used.

This is code-golf, so the shortest code, in bytes, wins.

Examples

n -> possible values of f_n | probabilities of values
1 -> 1 | 1
2 -> 1 | 1
3 -> 2, 0 | 1/2, 1/2
4 -> 3, 1, -1 | 1/4, 1/2, 1/4
5 -> 5, 3, 1, -1 | 1/8, 1/8, 3/8, 3/8
6 -> 8, 4, 2, 0, -2 | 1/16, 1/8, 1/4, 5/16, 1/4

• caird coinheringaahing: Sandbox
• Robin Ryder: May we assume \$n>2\$? (with 1-indexing)
• caird coinheringaahing: @RobinRyder, No you must handle the cases of \$n = 1\$ and \$n = 2\$
• Noodle9: Don't get why \$f_5\$ can't be \$-3=-1-2\$?
• caird coinheringaahing: @Noodle9 If \$f_3 = 2\,ドル because \$f_2\$ is always \1ドル\,ドル \$f_4\$ cannot be \$-1\,ドル it has to be either \2ドル - 1 = 1\$ or \2ドル + 1 = 3\$. Therefore, \$f_5\$ is any of \1ドル - 2 = -1\,ドル \1ドル + 2 = 3\,ドル \3ドル - 2 = 1\$ or \3ドル + 2 = 5\$

Answer 1

05AB1E, (削除) 8 (削除ここまで) 7 bytes

λ2D(‚Ω+

-1 byte thanks to @ovs.

Prints the infinite sequence.

Try it online.

Explanation:

λ # Create a recursive environment to output the infinite sequence,
 # implicitly starting at a(0)=1
 # (push a(n-1) implicitly)
 2 # Push a(n-2) (NOTE: all negative a(n) are 0, so a(-1)=0)
 D # Duplicate a(n-2)
 ( # Negate the copy: -a(n-2)
 ‚ # Pair them together: [a(n-2), -a(n-2)]
 Ω # Pop and push a random item
 + # And add it to the a(n-1)
 # (after which the infinite list is output implicitly)

• ovs: λ is really a good builtin for this challenge ;). 7 bytes: λ2D(‚Ω+.

Answer 2

APL (Dyalog Unicode), 20 bytes

{⍵,( ̄1*?2)⊥ ̄2↑⍵}/⎕⍴1

Try it online!

Takes n from stdin and prints first n terms.

{⍵,( ̄1*?2)⊥ ̄2↑⍵}/⎕⍴1 ⍝ Full program. Input: n
{ }/⎕⍴1 ⍝ Reduce a vector of n ones...
 ̄2↑⍵ ⍝ Last two items ([0 1] for the first iteration)
 ( ̄1*?2) ⍝ 1 or -1
 ⊥ ⍝ Base convert (or polynomial evaluate),
 ⍝ giving f(x-2)+f(x-1) or -f(x-2)+f(x-1) with 50% chance each
 ⍵, ⍝ Append to the previous iteration

Answer 3

Japt, (削除) 14 (削除ここまで) (削除) 13 (削除ここまで) 11 bytes

Outputs the nth term, 1-indexed. Uses JavaScript's Math.random() as seen here.

@Zä+iÍö)Ì}g

Try it, check the first n terms or view the distributions across 10,000 runs

@Zä+iÍö)Ì}g :Implicit input of integer U
@ :Function taking an array as argument via parameter Z
 Zä : Consecutive pairs of Z reduced by
 + : Literal "+"
 i : Insert
 Í : "n" at index 2 with wrapping, resulting in "n+"
 : (Hooray for shortcut abuse!)
 ö : Random character from that string, where XnY=Y-X
 ) : End reduction
 Ì : Get last element
 } :End function
 g :Starting with [0,1], repeatedly run it through that function,
 : pushing the result back to it each time
 :Implicit output of Uth element, 0-indexed

To explain how the shortcut abuse works here: Í is Japt's shortcut for n2<space> which is primarily intended to be used for converting binary strings to integers (e.g., "1000"Í="1000"n2 =8). However, when you pass a 2 character+space shortcut like that to another method - in this case i - the space is used to close that method and the 2 characters are split & passed to that method as separate arguments. Which is handy here as the i method for strings expects one argument containing the string to be inserted and another, optional integer argument for the index it's to be inserted at.

Answer 4

Jelly, 10 bytes

^{I'm pretty sure 10 is as good as it'll get in Jelly; I had some much longer solutions along the way.}

1ṫ-ḅØ-XṭƲ¡

A monadic Link accepting an integer, which yields all values up to and including that 0-indexed index
(i.e. \$n \to [f_0, f_1,\cdots, f_n]\ |\ f_0=f_1=1 : f_n = f_{n-1} \pm f{n-2} \$).

Try it online!

How?

1ṫ-ḅØ-XṭƲ¡ - Link: integer, n
1 - set the left argument to 1
 ¡ - repeat this n times:
 Ʋ - last four links as a monad f(left): e.g. left = [1,1,2,3,5,8]
 ṫ- - tail from 1-based, modular index -1 [5,8]
 (tailing 1 from index -1 yields [1])
 Ø- - signs (a nilad) [-1,1]
 ḅ - convert from base (vectorises) [3,13]
 (i.e. ×ばつ-1°, ×ばつ1°])
 X - random choice 3?
 ṭ - tack [1,1,2,3,5,8,3]

Answer 5

perl -061 -M5.010, (削除) 46 (削除ここまで) 43 bytes

say,ドルwhile(,,ドル$/)=($/,$/+,ドル-2*,ドル*(.5<rand))

Try it online!

This prints the infinite series.

Saved three bytes using a suggestion from Nahuel Fouilleul.

How does it work?

First trick is the command line switch -061. This sets the input record to 1 (as the ASCII value of 1 is 49, aka 61 in octal). The input record separator is $/.

We then use two variables to keep state, ,ドル, which initially is the empty string, but Perl will treat that as 0 when used as a number. $/ is set to 1, as discussed above. In an infinite loop, we set ,ドル to $/, and $/ to ,ドル + $/, and then, with probability .5, subtract 2 * ,ドル from the latter. We then print ,ドル.

• Nahuel Fouilleul: using while instead of redo can save 3 bytes Try it online!
• Nahuel Fouilleul: however as I understand the question the ouput should begin with 1,1 say should be before (saves only 2 bytes) Try it online!
• Abigail: If we use ,ドル instead of $y, and use say,ドルwhile... we still save three bytes. Try it online!
• Kjetil S: And say$/while($y,$/)=($/,.5>rand?$/+$y:$/-$y) saves another byte. Now 42.

Answer 6

Wolfram Language (Mathematica), 45 bytes

Outputs f(n) using RandomInteger 0 or 1

#&@@Nest[+##|(-1)^Random@0[[0]]#&@@#&,0|1,#]&

Try it online!

-6 bytes from @att

I also tried this 46 bytes

If[#>1,#0[#-1]+(-1)^RandomInteger[]#0[#-2],#]& 

but the sequence could not "remember" the previous values

• att: 45 bytes

Answer 7

Python 2, (削除) 66 (削除ここまで) 64 bytes

Outputs the sequence infinitely.

from random import*
a=b=1
while 1:print a;a,b=b,b+choice([-a,a])

Try it online!

Python 2, 73 bytes

Outputs the nth term of the sequence.

from random import*
a,b=0,1
exec"a,b=b,b+choice([-a,a]);"*input()
print a

Try it online!

• xnor: Nice solution! For the first one, you can initialize as a=b=1.

Answer 8

J, ²⁸ 22 bytes

-6 thanks to Bubbler!

0{1&({,]#.~_1^?@2)&1 1

Try it online!

0{1&({,]#.~_1^?@2)&1 1
 1& ... &1 1 a verb that will apply 1&... on 1 1 y (the input) times 
 ?@2 0 or 1
 _1^ 1 or _1
 ]#.~ to base, e.g. 3 5:
 (3* 1^1)+(5* 1^0) = 8 or
 (3*_1^1)+(5*_1^0) = 2
 {, prepend tail of list, i.e. 5 8 or 5 2
0{ take first element

• Bubbler: 22 bytes
• xash: @Bubbler really everything is solvable with base conversion. :-)

Answer 9

JavaScript (ES6), (削除) 68 67 66 53 (削除ここまで) 52 bytes

Saved 2 bytes thanks to @Shaggy

Returns the n-th term, 0-indexed.

f=(n,p=1,q=0)=>n?f(n-1,Math.random()<.5?p+q:p-q,p):p

Try it online!

Commented

f = ( // f is a recursive function taking:
 n, // n = 0-indexed input
 p = 1, // p = previous value
 q = 0 // q = penultimate value
) => //
 n ? // if n is not equal to 0:
 f( // do a recursive call:
 n - 1, // decrement n
 Math.random() // set p to either:
 < 0.5 ? p + q // p + q
 : p - q, // or p - q
 p // copy the previous value in q
 ) // end of recursive call
 : // else:
 p // return the last value

• Shaggy: 67 bytes, maybe?
• Shaggy: 52 bytes, I think.
• Arnauld: @Shaggy Yes, we definitely don"t need such a convoluted formula now that we're dealing with variables...
• Shaggy: Down to 50 bytes now, but I'm on my phone so you should probably double check the results.

Answer 10

><>, 22 bytes

1|.00<-x+40.08&:{&:}n:

Try it Online!

This is usually a terrible language for challenges involving randomness, since the only source of randomness in ><> is x.

But in this case things works out alright. x sends the instruction pointer in a random direction, so it either wraps around to itself in the y-direction, or hits a + or - with equal probability.

Answer 11

C (gcc), (削除) 58 57 (削除ここまで) 47 bytes

a,b;f(x){a=--x?f(b=x),b+=rand(x=b)%2?a:-a,x:1;}

Try it online!

• Saved 1 thanks to @ceilingcat
• Saved 10 thanks to @Dominic van Essen

Recursive solution which starts all the calls needed before executing them, the last call initialize values.

a,b; - aux variables
f(x){ - function tacking an integer n and 
 returning nth term 1 indexed.
a= - return trough eax register
--x?f(b=x) - call recursively before doing the job
x=b - local x used as temp
,b+=rand()%2?a:-a - rnd fib step
,x - assign temp(x) to a
:1;} - stop recursion and initialize a to 1

• Dominic van Essen: Nice. Q from a C newbie: why do you need to call srand() within the function? Isn't it Ok just to leave it however it was initialized already? It looks as if sequential calls still give random output without it, for only 47 bytes...
• AZTECCO: @Dominic van Essen unfortunately srand() has to be called to seed the rnd() function, if we don't do it every time we hit run we get always the same results, which is not truly random. In C rnd() pick values from a list and the standard way to use it is to seed rnd by calling srand ( time ( 0 ) ); which uses the current time to move the cursor on that list. Anyway in code-golf we can use a trick, we use an address (&x ) instead of time. It's the shortest way found so far.
• Peter Cordes: This being a function, you could argue that if your caller wants a different non-default random sequence, they can seed the PRNG. It's normal for C functions to use rand() without re-seeding it. Repeated calls to this function from the same caller (e.g. in a loop) will always get the same random number within one run of the program because stack ASLR (which indirectly randomizes &x) only happens once at process startup. If you don't re-seed, repeated calls will get later parts of one long random sequence. (Agreed with @DominicvanEssen)
• Dominic van Essen: This is exactly the gist of why I asked, but explained better! reseeding each cycle seems much less random to me than seeding once in the calling program, and not re-seeding any more.
• AZTECCO: @Dominic van Essen seems like the newbie here is me lol, thanks to both for pointing that out, I completely agree and update my answer!

Answer 12

R, (削除) 69 (削除ここまで) ... 55 bytes

-1 byte thanks to Giuseppe (which led to a further -4 bytes), and -1 byte thanks to Dominic van Essen (which led to a further -1 byte)

F=0:1;repeat cat(" ",{F=F[2]+F[1]*(0:-1)^sample(2)}[1])

Try it online!

Prints the sequence indefinitely, separated by spaces.

F is initialized as the vector [1 1].

At each step, draw a random permutation of the vector [1 2] with sample(2). This means that (0:-1)^sample(2) is either [0^1 (-1)^2]=[0 1] or [0^2 (-1)^1]=[0 -1] (with probability 1/2 each). In both cases, F[1] takes the previous value of F[2], and depending on the random draw, F[2] becomes either F[2]+F[1]or F[2]-F[1]. Finish the step by printing the first value of F.

Note that I can make this 2 bytes shorter by using a stupid delimiter between sequence values: Try online a 53 byte version which uses the string TRUE as delimiter.

• Giuseppe: 61, I think. I'm pretty sure it's valid, but haven't had a chance to really look at the distribution.
• Robin Ryder: @Giuseppe Well spotted, thanks! Calling cat first, as you suggested, but using repeat instead of while led to the current 57 byte solution.
• Dominic van Essen: 56 bytes, I think.
• Robin Ryder: @DominicvanEssen Good thinking, thanks! Furthermore, this allows a more efficient initialization of F, gaining another byte.

Answer 13

Raku, 26 bytes

{1,1,*+* *(-1,1).pick...*}

Try it online!

Outputs a lazy infinite list. This is pretty much identical to the normal fibonacci program, but with *(-1,1).pick tacked on to randomly flip the sign of the second parameter.

Answer 14

Python 3, 77 bytes

from random import*
f=lambda n,t=0,o=1:o if n<2else f(n-1,o,o+choice((-t,t)))

A recursive function which accepts \$n\$ and yields a possible \$f_n\$.

Try it online! Or see the first few as sampled 10K-distributions.

Answer 15

Red, 75 bytes

func[n][a: b: 1 loop n - 1[set[a b]reduce[b b +(a * pick[1 -1]random 2)]]a]

Try it online!

Returns the nth term.

Answer 16

x86 machine code, 21 bytes

The rdtsc version is the same size for x86-64 machine code.

rdrand reg (3 bytes) gives us a truly random number. Branching on its sign bit is cheap. By testing only 1 bit, the 50/50 probability is obviously satisfied exactly with zero bias.

rdtsc (2 bytes) gives us a "reference cycle" timestamp whose low bits are somewhat random (it takes at least 25 cycles to run back-to-back RDTSC instructions, but the counter isn't running that much faster than we're sampling it). Testing one bit with test al, 1 leads to significant correlation between consecutive decisions, but test al,al / jnp (branch on the parity flag, horizontal xor of the low 8 bits) gives surprisingly good results, and could be used on pre-IvyBridge machines that lack rdrand. Both of them golf to the same overall size in 32-bit mode.

Try it online! NASM listing for rdrand version: EAX rfib(ECX), callable from C with MS __fastcall

21 rfib: ;;; 0-indexed. ecx=5 gives the n=6 test case results.
22 00000020 31C0 xor eax, eax
23 00000022 99 cdq ; EDX = fib[-1] = 0
24 00000023 40 inc eax ; fib[0] = 1
25 00000024 E30E jecxz .done ; ecx=0 : return 1 without looping
27 .loop:
28 00000026 0FC7F7 rdrand edi
29 00000029 85FF test edi, edi ; 1 byte shorter than sar reg, imm / xor / sub 2's complement bithack
30 0000002B 7902 jns .no_negate ; the top bit is fully random
31 0000002D F7DA neg edx
32 .no_negate:
33 0000002F 0FC1D0 xadd eax, edx ; like xchg + add, and same size
34 00000032 E2F2 loop .loop
35 .done:
36 00000034 C3 ret
 size = 0x35 - 0x20 = 0x15 = 21 bytes

Note that xadd doesn't actually save any bytes vs. xchg eax, edx / add eax, edx. It's just fun. And it's "only" 3 uops, instead of 4 total, on Intel Skylake with register operands. (Normally the instruction is only used with the lock prefix and a memory destination, but it fully works with registers).

Test case:

 bash loop to test the ECX=5 case
$ asm-link -m32 -dn random-fib.asm &&
 { declare -A counts; counts=(); 
 for i in {1..10000}; do ./random-fib; ((counts[$?]++));done; 
 for i in "${!counts[@]}"; do echo "result: $(( i > 128 ? i-256 : i )): 
${counts[$i]} times";done }
result: 8: 617 times
result: 4: 1290 times
result: 2: 2464 times
result: 0: 3095 times
result: -2: 2534 times

---

NASM listing for rdtsc version: EBX rfib2(ECX). This version would be the same size in 64-bit mode; doesn't need 1-byte inc. RDTSC writes EAX and EDX so we can't take advantage of cdq in the init.

 2 rfib2: ; 0-index count in ECX, returns in EBX
 3 00000000 31F6 xor esi, esi
 4 00000002 8D5E01 lea ebx, [esi+1] ; fib[0] = 1, fib[-1] = 0
 5 00000005 E30D jecxz .done
 6 .loop:
 7 00000007 0F31 rdtsc ; EDX:EAX = TimeStamp Counter
 8 
 9 00000009 84C0 test al, al ; low bits are essentially random; high bits not so much
10 0000000B 7B02 jnp .no_negate
11 0000000D F7DE neg esi
12 .no_negate:
13 0000000F 0FC1F3 xadd ebx, esi
14 00000012 E2F3 loop .loop
15 .done:
16 ; returns in EBX
17 00000014 C3 ret
 size = 0x15 = 21 bytes

Test results for ECX=5:

result: 8: 668 times (ideal: 625)
result: 4: 1217 times (ideal: 1250)
result: 2: 2514 times (ideal: 2500)
result: 0: 3135 times (ideal: 3125)
result: -2: 2466 times (ideal: 2500)

vs. with test al, 1 / jnz to use just the low bit of the TSC as the random value:

 # test al,1 / jnz version: correlation between successive results.
result: 8: 115 times
result: 4: 79 times
result: 2: 831 times
result: 0: 3070 times
result: -2: 5905 times

test al,4 happens to work reasonably well for long runs on my Skylake CPU (i7-6700k) which ramps up to 3.9GHz at the energy_performance_preference=balance_performance I'm using, vs. a reference (TSC) frequency of 4008 MHz (more info on x86 constant-TSC stuff). I imagine there's some strange alchemy of branch prediction, and rdtsc itself having ~25 cycle throughput (core clocks) on Skylake (https://uops.info).

Results are generally better distributed with test al,al / jnp though, so prefer that to take entropy from all 8 low bits. When CPU frequency is low (idle), so the TSC is not close to the same frequency as the core, taking entropy from a single bit might work even better, although the parity of the low 8 bits is probably still best.

I haven't tested on a CPU with turbo disabled where non-boost core clock exactly equals the TSC reference clock. That could more easily lead to bad patterns if the rdtsc throughput happens to be a power of 2 or something, perhaps favouring some sequence that lets branch prediction lock on.

All my testing has been with one invocation of the function per process startup. A Linux static executable is pretty efficient to start up, but is still vastly more expensive than calling the function in a loop from inside the process.

• Peter Cordes: Related: x86-64 asm non-random Fibonacci, with the caller passing the first 2 sequence values: Golf a Custom Fibonacci Sequence

Answer 17

Wolfram Language (Mathematica), 38 bytes

Prints the sequence indefinitely. Adapted from J42161217's answer.

#0[Echo@+##,RandomChoice@{#,-#}]&[0,1]

Try it online!

Ungolfed:

f[a_, b_] := ( Echo[a+b]; f[a+b, RandomChoice[{a,-a}]] );
f[0, 1]

Answer 18

R, (削除) 55 (削除ここまで) (削除) 54 (削除ここまで) (削除) 53 (削除ここまで) (削除) 52 (削除ここまで) (削除) 51 (削除ここまで) (削除) 49 (削除ここまで) (削除) 48 (削除ここまで) 47 bytes

Edit: -1 byte, and again -1 byte thanks to Giuseppe, -1 byte thanks to AZTECCO

cat(1);repeat cat(" ",T<-sign(rt(1,1))*F+(F=T))

Try it online! or check the n=6 distribution.

Full program taking no input. Returns full random fibonacci sequence.

Program to return nth element using the same approach is 48 bytes.

Commented:

cat(1); # First, print the first element (1) 
 # (T is initialized to 1 by default,
 # and F is initialized to 0).
repeat # Now, repeat indefinitely:
 cat(" ", # output " ", followed by...
 T<- # T, updated to equal...
 sign(rt(1,1)) # the sign of 1 randomization of 
 # the t-distribution with 1 degree-of-freedom
 # (distribution is centred around zero,
 # so sign is [+1,-1] with probability [.5,.5])...
 *F # times F (second-last value)...
 +(F=T)) # plus T (last value)...
 # while updating F to equal T.

• Giuseppe: use rt(1,1) instead of rnorm(1), as it's a byte shorter :-)
• Dominic van Essen: Thanks Giuseppe! I started going-through all of the r... functions, but got swamped when I realised that I didn't understand the parameters for most of them...!
• Dominic van Essen: (had some browser refreshing problems, so hopefully only posted once now...)
• Giuseppe: + coerces it's arguments to numeric if possible, so +T should work for another byte down.

Answer 19

Dotty, 75 bytes

val| :Stream[Int]=1#::1#::(|zip|.tail map(_*((math.random*2).toInt*2-1)+_))

Try it online

Same as below.

Scala, (削除) 91 (削除ここまで) (削除) 87 (削除ここまで) (削除) 85 (削除ここまで) 84 bytes

Saved 4 bytes thanks to corvus_192

val| :Stream[Int]=1#::1#::(|zip|.tail map{t=>t._2+t._1*((math.random*2).toInt*2-1)})

Try it online

| is a Stream so that previous elements are remembered. To get the nth element, you can use |(n-1) (it's 0-indexed). To get the first n elements, use |.take(n) (l.take(n).toList to force it).

• corvus_192: You can save a few byte by using Stream instead of LazyList and dropping the () from math.random.

Answer 20

Charcoal, 28 bytes

×ばつθ⊖⊗‽2ι≔ηθ≔ιη»Iθ

Try it online! Link is to verbose version of code. Outputs the nth number. Explanation:

≔0θ≔1η

Start with 0 as the ith number and 1 as the i+1th number.

FN«

Loop n times.

×ばつθ⊖⊗‽2ι

Calculate the next number.

≔ηθ≔ιη

Shuffle the values around.

»Iθ

Output the nth number.

29 bytes to output the first n numbers:

×ばつ§υ±2⊖⊗‽2I✂υ0±2

Try it online! Link is to verbose version of code. Explanation:

F2⊞υ1

Start with 1 as the first and second numbers.

FN

Loop n times.

×ばつ§υ±2⊖⊗‽2

Calculate the next number.

I✂υ0±2

Output all but two of the numbers.

Answer 21

Icon, 70 bytes

procedure n()
f:=[1,1]
while write(f[2])&push(f,f[1]+?[1,-1]*f[2])
end

Try it online!

Prints the sequene indefinitely.

Answer 22

C (gcc), (削除) 56 (削除ここまで) (削除) 53 (削除ここまで) 52 bytes

Edit: -3 bytes thanks to AZTECCO, -1 byte thanks to ceilingcat

x;y;r(n){for(x=y=1;--n;)x=~-(rand()&2)*y+(y=x);x=y;}

Try it online!

Non-recursive answer in C.
Function that returns nth (one-based) element of random fibonacci sequence.

x;y; # x & y hold last and last-but-one elements;
r(n){ # n is index of element we're looking for;
for(x=y=1; # initialise first two elements to 1;
 --n;) # now loop by decreasing n until it is zero,
 x= # update x to become equal to:
 ~-(rand()&2)*y # plus-or-minus y...
 +(y=x) # plus x
 # (while updating y to equal the current x).
 ;x=y;} # after looping, return y.

Note: Following some discussion in the comments here and in AZTECCO's answer, a consensus was reached that it is not necessary to initialize the random seed within a function. Of course, that this means that the calling program should do so, or the function may give the same sequence of pseudo-random output every time the calling program is run. A 74 byte variant of the function can itself initialize the random seed itself (but only on first call, so that subsequent calls from the same program run give different output).

• AZTECCO: You can use --n instead of n-=n>0 . I think you have to seed rnd. See my coment on my answer.
• Dominic van Essen: @AZTECCO - Thanks for your explanation about seeding rand(): I've added variants here that now include this, so that our answers can be compared (yours is better!), but I'm not completely convinced that re-seeding every cycle is necessary or even desirable. It'd be interesting to know the consensus of C-golfers about this...
• Dominic van Essen: @AZTECCO - I think that --n causes a bug when calling r(0) (to get the first element in the sequence): this is why I used the much-more-complicated n-=n>0. If I'm missing something, please tell me!
• Peter Cordes: Other C randomness answers have just used rand() without srand(). e.g. Randomizing until 0 and another C answer on the same question. In a function, it makes total sense that you seed the PRNG once at process startup, so it's not your responsibility and in fact you should not do that. If you were writing a whole program (e.g. a main) then it would make sense and arguably be required depending on the challenge, @AZTECCO.
• AZTECCO: @Dominic van Essen sorry, I didn't noticed it was 0 based, you can switch to 1 based like this and should be fine

Answer 23

Bash, 65 bytes

a=1;b=1;while :;do echo $a;t=$b;:$[b+=$RANDOM&1?$a:-$a];a=$t;done

Try it online!

Endlessly outputs the latest and greatest version of the sequence.

Answer 24

Swift, 77 bytes

sequence(first:(1,1)){a,b in(b,.random() ?a+b:a-b)}.lazy.forEach{print(0ドル.0)}

Outputs until Int overflow.

Answer 25

Lua, 81 bytes

t={1,1}for i=1,...do t[i]=t[i]or t[i-1]+t[i-2]*(math.random(2)*2-3)print(t[i])end

Try it online!

Takes number of members to be printed as an argument. Replace ... with 1/0 to print sequence forever at const of one byte.

Answer 26

Vyxal, 9 bytes

‡(+-c/od11Ḟ

Try it Online!

Prints the infinite list.

 Ḟ # Create an infinite list from...
 11 # [1, 1]
‡ d # And a function taking two arguments...
 ( c/o # Choose randomly from...
 +- # sum of previous two, difference of previous two

Answer 27

Excel VBA, (削除) 49 (削除ここまで) 48 bytes

^{Saved 1 byte thanks to Taylor Raine and using the VBA native function instead of evaluating the Excel function.}

b=1:Do:c=a+b*IIf(Rnd()<.5,1,-1):a=b:b=c:?a:Loop

Code is input and run in the immediate window. Output is the infinite sequence. Here's what it looks like if it was formatted into a subroutine instead:

b = 1
Do
 c = a + b * IIf(Rnd() < .5,1,-1)
 a = b
 b = c
 Debug.Print a
Loop

The Rnd() function outputs a value in the range [0,1) hence the <.5 check. I out the 6th term in the sequence 1,000 times (since that's an example in the question) and found the following distribution of values:

Value	Count	Percent
-8	45	4.5%
-4	48	4.8%
-2	252	25.2%
0	322	32.2%
2	264	26.4%
4	47	4.7%
8	22	2.2%

• Taylor Raine: Why not use IIf(Rnd()<.5,1,-1)?