Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
Given positive integer n, generate a(n).
n a(n)
1 1
2 1
3 2
4 3
5 3
6 4
7 5
8 5
9 6
10 6
11 6
12 8
13 8
14 8
15 10
16 9
17 10
18 11
19 11
20 12
a n|n<3=1|b<-a.(-)n=b(b 1)+b(b 2)
Defines a function a.
(b.b)1+(b.b)2 be shorter than the sum?
\$\endgroup\$
Byte count assumes ISO 8859-1 encoding.
.+
$*;1¶1¶
+`;(?=(1)+¶(1)+)(?=(?<-1>(1+)¶)+)(?=(?<-2>(1+)¶)+)
$3$4¶
G3=`
1
Try it online! (The first line enables a linefeed-separated test suite.)
I'll have to golf this some more later.
!n=n<3||!(n-!~-n)+!(n-!~-~-n)
We redefine the unary operator ! for our purposes.
If n is 1 or 2, n<3 returns true and this is our return value.
If n larger than 2, n<3 returns false and the || branch gets executed. This is a straightforward implementation of the definition, where ~-n yields n - 1 and ~-~-n yields n - 2.
0000000: eefb5b 04f83a a75dc2 36f8d7 cf6dd0 af7b3b 3ef8d7 ..[..:.].6...m..{;>..
0000015: cfed12 f661f0 ae9d83 ee63e6 065df7 ce6183 af7383 ....a.....c..]..a..s.
000002a: 76ef3c 3f6383 7eff9c b9e37f v.<?c.~.....
set numin
set numout
add 1
fwd 1
add 1
fwd 6
get
sub 1
jmp
jmp
sub 1
fwd 1
add 1
rwd 1
jnz
fwd 1
sub 1
rwd 2
add 2
jmp
rwd 4
jmp
sub 1
fwd 3
add 1
rwd 3
jnz
fwd 4
jmp
sub 1
rwd 3
add 1
rwd 1
add 1
fwd 4
jnz
rwd 3
jmp
sub 1
fwd 3
add 1
rwd 3
jnz
fwd 4
add 2
jmp
rwd 5
jmp
rwd 1
jmp
sub 1
fwd 2
add 1
rwd 2
jnz
fwd 1
jmp
sub 1
rwd 1
add 1
fwd 1
jnz
rwd 1
sub 1
jnz
fwd 2
jmp
sub 1
rwd 1
add 1
rwd 1
add 1
fwd 2
jnz
fwd 1
jmp
rwd 2
jmp
sub 1
fwd 1
add 1
rwd 1
jnz
fwd 2
jmp
sub 1
rwd 2
add 1
fwd 2
jnz
fwd 1
jnz
fwd 3
sub 1
jnz
rwd 2
jmp
sub 1
rwd 3
add 1
fwd 3
jnz
fwd 1
sub 1
jnz
fwd 2
jnz
rwd 7
put
Or in Brainfuck notation:
+>+>>>>>>,-[[->+<]>-<<++[<<<<[->>>+<<<]>>>>[-<<<+<+>>>>]<<<[->>>+<<<]>>>>++[<<<<<[<
[->>+<<]>[-<+>]<-]>>[-<+<+>>]>[<<[->+<]>>[-<<+>>]>]>>>-]<<[-<<<+>>>]>-]>>]<<<<<<<.
Saved 1 byte thanks to @Dennis
Every answer is the same, I must do something different!
a(n){return n<3?:a(n-a(n-2))+a(n---a(n));}
Explanation: it's basically a(n-a(n-2))+a(n-a(n-1)) but with swaggyundefinedbehavior (works on my phone (gcc) and ideone).
1 between ? and :.
\$\endgroup\$
$b+=$b[$_-$b[$_-2]]+$b[$_---$b[$_]]
\$\endgroup\$
Jul 29, 2016 at 20:28
Byte count assumes ISO 8859-1 encoding and Mathematica's $CharacterEncoding set to WindowsANSI (the default on Windows; other settings might work as well, but some like UTF-8 definitely don't).
±1=±2=1
±n_:=±(n-±(n-1))+±(n-±(n-2))
Defines ± as a unary operator.
I tried getting rid of the duplication, but ended up with the same byte count:
±1=±2=1
±n_:=Tr[±(n-±(n-#))&/@{1,2}]
2Rạ⁸߀$⁺Sµ1>?2
Try it online! or verify all test cases (takes a few seconds).
2Rạ⁸߀$⁺Sµ1>?2 Main link. Argument: n (integer)
2R Yield [1, 2].
$ Combine the previous three links into a monadic chain.
⁸ Yield n.
ạ Take the absolute difference of the return value and n.
߀ Recursively call the main link on each result.
⁺ Duplicate the chain.
The first copy maps [1, 2] to [a(n - 1), a(n - 2)].
The second copy maps [a(n - 1), a(n - 2)] to
[a(n - a(n - 1)), a(n - a(n - 2))].
S Take the sum.
µ Combine all links to the left into a chain.
? If...
> 2 n is greater than 2, call the chain.
1 Else, return 1.
A recursive solution in ES6. Any golfing tips much appreciated.
a=n=>n>2?a(n-a(n-1))+a(n-a(n-2)):1
Thank you to /u/ismillo for shortening even further.
ịḣ2S;
1Ç⁸¡2ị
This is an iterative approach.
Try it online! or verify all test cases.
1Ç¡2ị Main link. Argument: n
1 Set the return value to 1.
Ç¡ Call the helper link n times, updating the return value after each call.
2ị Extract the second element of the resulting array.
ịḣ2S; Helper link. Argument: A (array)
ị At-index; retrieve the elements of A at the values of A.
ḣ2 Head 2; extract the first two results.
S Take the sum of the result.
; Prepend the sum to A.
a=lambda n:n<3or a(n-a(n-1))+a(n-a(n-2))
Simple naïve interpretation of the challenge.
Saved 5 bytes thanks to @LeakyNun!
h n|n<3=1|n>2=h(n-h(n-1))+h(n-h(n-2))
exactly like described in the challenge, using guards
n<3 for h 2 to be 1.
\$\endgroup\$
a=function(n)ifelse(n<3,1,a(n-a(n-1))+a(n-a(n-2)))
Usage:
> a(1)
1
> a(20)
12
int a(int n)=>n<3?1:a(n-a(n-1))+a(n-a(n-2));
i wonder if this can be shortened by making it anonymous
thanks pinkfloydx33!
int a(int n)=>n<3?1:a(n-a(n-a))+a(n-a(n-2));
\$\endgroup\$
Jul 29, 2016 at 18:57
-a in the first set of parens should be -1
\$\endgroup\$
Jul 30, 2016 at 10:16
{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
Explanation:
{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
⍵≤2:1 If argument is 2 or less, return 1
⋄ Otherwise:
⍵-⍳2 Subtract [1, 2] from the argument
∇¨ Recursive call on both
⍵- Subtract both results from the argument
∇¨ Recursive call on both again
+/ Sum
Non-recursive, since I want this to work for n=100000, say:
Function A(N):ReDim B(N):For i=3 To N:B(i)=B(i-B(i-1)-1)+B(i-B(i-2)-1)+1:Next:A=B(N)+1
... and press return (byte #87) at the end of the line to get the End Function statement for "free". Note that B values are offset by -1 to avoid initializing for n=1 and 2.
Invoke in spreadsheet as normal, eg =A(100000) to get 48157
The recursive version, 61 bytes,
Function Y(N):If N<3 Then Y=1 Else Y=Y(N-Y(N-1))+Y(N-Y(N-2))
starts to get unreasonably slow for n>30, and couldn't be said to work at all for n>40.
A direct implementation. Any golfing suggestions are welcome.
a=->n{n<3?1:a[n-a[n-1]]+a[n-a[n-2]]}
a[n-1] and such, the function needs to be named.
\$\endgroup\$
Aug 3, 2016 at 11:04
17 saved thanks to Leaky Nun.
int a(int n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}
int a(int n){return n<3?1:a(n-a(n-2))+a(n---a(n));}, but unfortunately it uses the same amount of bytes as the answer you already have.. Also, I would specify that your answer is in Java 7, since the Java 8 answer would be shorter: n->return n<3?1:a(n-a(n-1))+a(n-a(n-2)) (39 bytes).
\$\endgroup\$
Aug 3, 2016 at 12:44
Non-competing, since the language postdates the challenge. Thanks to Kenny Lau for saving 4 bytes. Code:
ece+V
Expanded form (V is short for 11):
a(n) = ece+
a(0) = 1
a(1) = 1
Code:
e # Stack is empty, so a(n - 1) is used, and it calculates a(n - a(n - 1))
c # Calculate a(n - 2)
e # Calculate a(n - a(n - 2))
+ # Add up
Try it online!. Calculates n = 1000 in 0.1 seconds.
param($n)$b=1,1;2..$n|%{$b+=$b[$_-$b[$_-1]]+$b[$_-$b[$_-2]]};$b[$n-1]
Takes input $n, sets $b to be an array of @(1, 1), then enters a loop from 2 .. $n. Each iteration we tack onto $b the latest calculation in the sequence with a simple += and the definition of the sequence. We then output the appropriate number from $b (with a -1 because arrays in PowerShell are zero-indexed). This works if $n is 1 or 2 because both of those values are pre-populated into the lower indices of $b from the start, so even if the loop tacks on junk, it's ignored anyway.
$a={param($k)if($k-lt3){1}else{(&$a($k-(&$a($k-1))))+(&$a($k-(&$a($k-2))))}}
First time I've used the equivalent of a lambda as the answer, as usually an iterative solution is shorter (as you can see from all the nested parens). But, in this case, the nested parens are almost duplicated in the iterative solution with the nested array calls, so the recursive solution is shorter. Nope, the iterative solution is indeed shorter (see above).
Call it via the execution-operator, like &$a 20. Just a straight-up recursive call.
n=>[...Array(n+1)].reduce((p,_,i,a)=>a[i]=i<3||a[i-p]+a[i-a[i-2]])
Non-recursive version for speed; recursive version is probably shorter but I'll leave it for someone else to write. I always like it when I get to use reduce. Note: 1 byte saved by returning true (which casts to 1 when used in an integer context) for of a(1) and a(2).
L|<b3smy-bytdtBb
L def y(b):
|<b3 b < 3 or …
m tBb map for d in [b - 1, b]:
y-bytd y(b - y(d - 1))
s sum
Defines a function y.
Try it online
(added yMS20 to print the first 20 values)
I finally got it working!
: Q recursive dup dup 3 < if - 1+ else 2dup 2 - Q - Q -rot 1- Q - Q + then ;
Explanation:
: Q recursive \ Define a recursive function Q
dup dup 3 < \ I moved a dup here to golf 2 bytes
if \ If n < 3, return 1
- 1 \ Golf: n-n is zero, add one. Same as 2drop 1+
else
2dup 2 - Q - Q \ Copy n until 4 on stack, find Q(n-Q(n-2))
-rot \ Move the result below 2 copies of n
1- Q - Q + \ Find Q(n-Q(n-2)), then add to previous ^
then ;
Try it online (slightly un-golfed from above)
Unfortunately, mutual recursion is a bit too wordy to use for golfing.
function a(n)return n<3 and 1 or a(n-a(n-1))+a(n-a(n-2))end
a:=n->`if`(n>2,a(n-a(n-1))+a(n-a(n-2)),1)
Usage:
> a(1);
1
> a(20);
12
This problem is certainly a good candidate for memoization. Using option cache, the run times are cut down significantly:
aC := proc(n)
option cache;
ifelse( n > 2, aC( n - aC(n-1) ) + aC( n - aC(n-2) ), 1 );
end proc:
This can be seen using:
CodeTools:-Usage( aC(50) );
No big shenanigans, just recursively calculates the result.
§2?1:ßU-ßUÉ)+ßU-ßU-2
§2 // If the input is less than or equal to 2
?1 // return 1,
: // otherwise
ß // recursively recall with
U-ßUÉ // input minus recursive recall input minus one
)+ // plus
ßU-ßU-2 // same with input minus two.
1:`(+&$:/@:-$:@-&1 2)@.(2&<)
Uses the recursive definition.
Extra commands are used for formatting multiple input/output.
f =: 1:`(+&$:/@:-$:@-&1 2)@.(2&<)
(,:f"0) >: i. 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12
1:`(+&$:/@:-$:@-&1 2)@.(2&<) Input: n
2&< If n < 2
1: Return 1
Else
-&1 2 Subtract [1, 2] from n to get [n-1, n-2]
$:@ Call recursively on n-1 and n-2
- Subtract each of the results from n
/@: Reduce using
$: A recursive call on each
+& Then summation
Return that value as the result
