22
Python 2, 27 bytes
lambda L:(2*L*L-2)**.5//1+3
Try it online!
A direct formula:
$$ f(L) = \lfloor \sqrt{2 L^2-2}\rfloor + 3 $$
Derivation
As noted by @Kirill L. and others, the optimal layout uses a near-diagonal line segment whose horizontal and vertical span are at least \$(h,h)\$ or \$(h,h+1)\$. We need the length-\$L\$ to cover at least this much ...
12
R, 79 77 bytes
L=scan();j=1:L;a=j*2^.5;b=Mod(j+j*1i+1i);3+2*sum(L>a)+max(a[L>a],b[L>b])%in%b
Try it online!
Note: as it turned out, this is completely destroyed by xnor's formula, which would be 23 bytes in R:
(2*scan()^2-2)^.5%/%1+3
However, I'm keeping the existing code as a reference to my original solution.
Original explanation
In general ...
11
Jelly, 6 bytes
3Ḋ*)SI
Try it online!
-1 byte thanks to Jonathan Allan
1-indexed sequence without leading zeros. Uses the formula \$\sum_{k=1}^{n} 3^k - 2^k\$.
Explanation
3Ḋ*)SI Main monadic link
) For each k in the range [1..n]:
3Ḋ Remove the first element from the range [1..3]
* Raise each to the power of k
S Sum (producing [sum(2^k)...
8
R, 23 bytes
3^(n=scan()+2)/2-2^n+.5
Try it online!
Outputs without the leading zeros, 0-indexed.
Uses formula from OEIS page:
$$ a(n) = 9 \cdot 3^n/2 - 4 \cdot 2^n + 1/2 $$
8
Jelly, 7 bytes
cþæ*2FS
Try it online!
Now that xigoi has outgolfed me, I thought I'd share my answer.
This outputs the \$n\$ term of the sequence without leading zeroes.
How it works
We generate the matrix
$$\left[\begin{matrix}
\binom 1 1 & \binom 2 1 & \cdots & \binom n 1 \\
\binom 1 2 & \binom 2 2 & \cdots & \binom n 2 \\
\vdots &...
7
Hexagony, 5 bytes
L;o>l
Try it online!
Hexagony golfing language confirmed
For some reason I was looking at my own answer that prints "six" in 6 bytes and randomly thought "what if I remove @?", and exactly got this answer. 4 bytes is impossible because Lol; is already 4 bytes and it is impossible to alternate two chars and print both ...
7
Alchemist, 76 bytes
_+0j->2c
b+0j->3d
0j+0_+0b->j
c+j+x->_+j
d+j->x+b+j
j+0c+0d->Out_x+Out_" "!b
Try it online!
Outputs nonzero values infinitely using the formula \$S(n, 3) = \sum_{k=1}^{n-2} (3^k - 2^k)\$.
On TIO, this computes up to the 13th element (2375101) before timing out.
6
Python 2, 24 bytes
lambda n:3**n/6-~-2**n/2
Try it online!
Formula from OEIS for \$n>0\$:
$$ f(n) = \frac{1}{2}(3^{n-1}-2^n+1)$$
6
APL (Dyalog Unicode), 14 bytes
Anonymous tacit prefix function using xnor's formula. 1-indexed.
2÷⍨1-2∘*-3*-∘1
Try it online!
6
Jelly, 9 bytes
Port of xnor's answer, made/fixed and golfed with hyper-neutrino's and caird coinheringaahing's help.
’3*_2*$‘H
Try it online!
This doesn't handle leading zeroes.
’3*_2*$‘H
’ n-1
3* 3^(n-1)
_ From that, subtract
2*$ 2^n
‘ Increment that
H Halve it
6
Jelly, 12 bytes
3ẹ@þṗ¥ẠƇṢ€QL
Try it online!
A monadic link that takes \$n\$ as its argument and returns \$a(n)\$. This is longer and less efficient than the answers based on the OEIS formulae, but should work for any value of \$k\$ by varying the first number in the link from 3.
Also, removing the L at the end yields the actual sets.
Explanation
3 ¥ ...
6
Jelly, 9 bytes
Surely there is an eight or less out there...
1×Ɱ3$¡FQS
A full program that accepts a non-negative integer from STDIN and prints the result using the 0-indexed, no leading zeros option.
Try it online!
How?
1×Ɱ3$¡FQS - Main Link: no arguments
1 - start with x=1
¡ - repeat this (read from STDIN) times:
$ - last two ...
5
Scala, 132 bytes
n=>(for{i<-1 to n-1
j<-i+1 to n-1
p<-1.to(n).permutations}yield{Set(p.slice(0,i),p.slice(i,j),p.slice(j,n))map(_.toSet)}).toSet.size
Try it online!
Is it short? No. Is it efficient? No. Is it clever? No. Why did I make it? I...don't know. I'll try golfing it later, if possible.
4
Jelly, 13 bytes
Thanks to @ovs for the fix.
%Lċ0
*ṗ’ÇƤ€QL
Try it online!
The first line computes the shadow transform.
The second line looks at the shadow transform of all sequences of length n with elements in {1, 2, ..., n^n}.
4
J, 28 bytes
-1 thanks to Jonah!
The optimal is always either the diagonal L, L with 3+2*L tiles crossed as noted by @Kirill L. or L, L+1, in which case an extra tile is crossed.
((>]+&.*:>:)+3+2*])[<.@%%:@2
Try it online!
[<.@%%:@2 calculate L by dividing n by sqrt(2), then flooring
3+2*] 3+2*L
]+&.*:>: calculate length to L, L+1
>...
4
C (gcc), 34 bytes
f(n){n=n<3?0:5*f(n-1)-6*f(n-2)+1;}
Try it online!
Inputs \$0\$-based \$n\$.
Returns \$S(n,3)\$.
Uses the formula: \$a(n) = 5\cdot a(n-1) - 6\cdot a(n-2) + 1\$, for \$n > 2\$.
4
Wolfram Language (Mathematica), 15 bytes
#~StirlingS2~3&
Try it online!
4
Rattle, 24 bytes
|s>-s=3e~s<=2e~sg1-~+/R1
Try it Online!
This is a port of xnor's Python answer into Rattle using this formula:
$$ f(n) = \frac{1}{2}(3^{n-1}-2^n+1)$$
Explanation
| takes the user's input
s saves the user's input (n) to memory slot 0
> move pointer right
- ...
4
Factor + math.extras, 18 bytes
[ 3 + 3 stirling ]
Ignoring leading zeroes. Zero-indexed. stirling is bugged in the build TIO uses. It was fixed about three years ago, so here's a picture of running it in the listener with a more recent build.
4
Python 3, 67 bytes
Prints the 0-based sequence forever.
d=n=k=0
while 1:k+=1;k**=k*k<=n;n+=k<2;k+n&1<(k>1%n)!=print(d);d+=1
Try it online!
Commented:
d=n=k=0
while 1:
k+=1 # increment k
k**=k*k<=n # k=k**1=k if k*k<=n, else k=k**0=1
n+=k<2 # increment n if k is equal to 1
...
3
Jelly, 18 17 8 bytes
-9 using xnor's mathematical simplification of the same method as the 17, below.
²Ḥ_2ƽ+3
A monadic Link that accepts a positive integer, \$L\$ and yields the maximal squares touched.
Try it online! Or see the test-suite.
How?
²Ḥ_2ƽ+3 - Link: positive integer, L
² - square -> L²
Ḥ - double -> 2L²
_2 - ...
3
Python 2 (PyPy), 228 225 bytes
This is based on the first PARI implementation on OEIS and computes terms up to \$n=6\$ on TIO.
import math,itertools as I
L=math.log
R=range
n=input()
P=k=r=1
while k<n:k+=1;r*=k**int(P%k*L(n+.5)/L(k));P*=k*k
print len({tuple(sum(x%o<1for x in s[:o])for o in R(n))for s in I.product(*[[i+1for i in R(r)if-1<r%~i]]*~-n)}...
3
Flipbit, 35 30 28 bytes
Thanks to Bubbler for -5 by shortening the loop
Thanks to ovs for -2 by being big smort
^>>>^>^>>.<<<<<^>>>[>^>^.<<]
Try it online!
Prints L, gets the tape set up for l, then makes use of the fact that o and l differ by only their two least significant bits to create a short loop ...
3
APL (Dyalog Unicode), 14 bytes
-/3 2⊥¨∘⊂1,⍴∘1
Try it online!
A function implementing the sum formula using base conversion:
$$
a(n) = \sum_{k=0}^n \left( 3^k-2^k \right) = \sum_{k=0}^n 3^k - \sum_{k=0}^n 2^k = (\underbrace{1 \cdots 1}_{n+1})_3 - (\underbrace{1 \cdots 1}_{n+1})_2
$$
⍴∘1 ⍝ a vector of n 1's
1, ⍝ prepend an ...
3
Vyxal sr, 6 bytes
ƛ23fe¯
Try it Online!
A port of xigoi's Jelly answer
Explained
ƛ23fe¯
ƛ # over the range [1, input] (call each item n)
23f # the list [2, 3]
e # ^ ** n
¯ # deltas of ^
# the s flag auto-sums the result
```
2
FALSE, 13 bytes
'L,[1]["ol"]#
Try it online!
Explanation
'L, // outputs "L" character
[1] // pushes lambda which evaluates to 1 onto the stack
["ol"] // pushes lambda which prints "ol" onto the stack
# // Executes lambda on top of stack while the lambda below it
// does not evaluate to zero
Note: This is my ...
2
Perl 5, 73 bytes
for$d(0,1){$w=0;1while$w**2+($d+$w++)**2<$_**2;$m+=2*$w-1+$d}$_=int$m/2+1
Try it online!
Took @Kirill L.'s explanation and ran with it. Does two passes, without and with "deviation" in $d. The int$m/2+1 outputs the average (rounded up if .5) of those two passes, which will be the max of those two results. Reads the wanted ...
2
Vyxal, 7 bytes
*d⇩√3+⌊
Try it Online!
Shameless port of xnor's answer
* # Square
d # Double
⇩ # Subtract 2
√ # Square root
3+ # Add 3
⌊ # Floor
2
Japt, 10 bytes
Ò2nU²Ñ ¬ÄÄ
Try it
Ò2nU²Ñ ¬ÄÄ :Implicit input of integer U
Ò :Negate the bitwise NOT of (i.e., floor and increment)
2n : Subtract 2 from
U² : U squared
Ñ : Times 2
¬ : Square root
ÄÄ :Add one twice
2
Risky, 10 bytes
+0?+1+_0+0__!2?-+_{0
Try it online!
1-indexed sequence without leading zeros. Uses the formula \$\sum_{k=0}^{n} 3^k - 2^k\$.
Explanation
+ sum
0 range
? n
+ +
1 1
+ copy-last
_
0 0
+ +
0 0
_ map
_
! 3
2 ^
? k
- -
+ 2^
_ [k,n]
{ ...
Only top voted, non community-wiki answers of a minimum length are eligible
