36
\$\begingroup\$

Single moves

The board is an infinite 2 dimensional square grid, like a limitless chess board. A piece with value N (an N-mover) can move to any square that is a distance of exactly the square root of N from its current square (Euclidean distance measured centre to centre).

For example:

  • A 1-mover can move to any square that is horizontally or vertically adjacent
  • A 2-mover can move to any square that is diagonally adjacent
  • A 5-mover moves like a chess knight

Note that not all N-movers can move. A 3-mover can never leave its current square because none of the squares on the board are a distance of exactly root 3 from the current square.

Multiple moves

If allowed to move repeatedly, some pieces can reach any square on the board. For example, a 1-mover and a 5-mover can both do this. A 2-mover can only move diagonally and can only reach half of the squares. A piece that cannot move, like a 3-mover, cannot reach any of the squares (the starting square is not counted as "reached" if no movement occurs).

1-mover 2-mover 3-mover 4-mover 5-mover 8-mover 9-mover 10-mover 20-mover 25-mover 40-mover 64-mover 65-mover 68-mover

The images show which squares can be reached. More details on hover. Click for larger image.

  • Squares reachable in 1 or more moves are marked in black
  • Squares reachable in exactly 1 move are shown by red pieces
    (apart from the 3-mover, which cannot move)

What proportion of the board can a given N-mover reach?

Input

  • A positive integer N

Output

  • The proportion of the board that an N-mover can reach
  • This is a number from 0 to 1 (both inclusive)
  • For this challenge, output as a fraction in lowest terms, like 1/4, is allowed

So for input 8, both 1/8 and 0.125 are acceptable outputs.

Scoring

This is code golf. The score is the length of the code in bytes. For each language, the shortest code wins.

Test cases

In the format input : output as fraction : output as decimal

  1 : 1     : 1
  2 : 1/2   : 0.5
  3 : 0     : 0
  4 : 1/4   : 0.25
  5 : 1     : 1
  6 : 0     : 0
  7 : 0     : 0
  8 : 1/8   : 0.125
  9 : 1/9   : 0.1111111111111111111111111111
 10 : 1/2   : 0.5
 13 : 1     : 1
 16 : 1/16  : 0.0625
 18 : 1/18  : 0.05555555555555555555555555556
 20 : 1/4   : 0.25
 25 : 1     : 1
 26 : 1/2   : 0.5
 64 : 1/64  : 0.015625
 65 : 1     : 1
 72 : 1/72  : 0.01388888888888888888888888889
 73 : 1     : 1
 74 : 1/2   : 0.5
 80 : 1/16  : 0.0625
 81 : 1/81  : 0.01234567901234567901234567901
 82 : 1/2   : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1     : 1
146 : 1/2   : 0.5
148 : 1/4   : 0.25
153 : 1/9   : 0.1111111111111111111111111111
160 : 1/32  : 0.03125
161 : 0     : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0     : 0
164 : 1/4   : 0.25
241 : 1     : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4   : 0.25
245 : 1/49  : 0.02040816326530612244897959184
260 : 1/4   : 0.25
261 : 1/9   : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2   : 0.5
292 : 1/4   : 0.25
293 : 1     : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1     : 1
326 : 0     : 0
360 : 1/72  : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2   : 0.5
369 : 1/9   : 0.1111111111111111111111111111
370 : 1/2   : 0.5
449 : 1     : 1
450 : 1/18  : 0.05555555555555555555555555556
488 : 1/8   : 0.125
489 : 0     : 0
490 : 1/98  : 0.01020408163265306122448979592
520 : 1/8   : 0.125
521 : 1     : 1
522 : 1/18  : 0.05555555555555555555555555556
544 : 1/32  : 0.03125
548 : 1/4   : 0.25
549 : 1/9   : 0.1111111111111111111111111111
584 : 1/8   : 0.125
585 : 1/9   : 0.1111111111111111111111111111
586 : 1/2   : 0.5
592 : 1/16  : 0.0625
593 : 1     : 1
596 : 1/4   : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2   : 0.5
611 : 0     : 0
612 : 1/36  : 0.02777777777777777777777777778
613 : 1     : 1
624 : 0     : 0
625 : 1     : 1
\$\endgroup\$
  • 8
    \$\begingroup\$ I posted this question on Math.SE: math.stackexchange.com/questions/3108324/… \$\endgroup\$ – infmagic2047 Feb 11 at 4:27
  • \$\begingroup\$ Interesting conjecture! \$\endgroup\$ – trichoplax Feb 11 at 10:06
  • 1
    \$\begingroup\$ "A piece that cannot move, like a 3-mover, cannot reach any of the squares". Interestingly enough, even if you count the starting square, since the board is infinite, it still converges to 0 as a proportion. \$\endgroup\$ – Beefster Feb 11 at 17:10
  • \$\begingroup\$ @Beefster good point. I went with this way to make the limit easier to find without having to go all the way to infinity... \$\endgroup\$ – trichoplax Feb 11 at 18:13
  • 1
    \$\begingroup\$ @infmagic2047 's math.se question about the prime factoring approach now has an answer with a complete proof. \$\endgroup\$ – Ørjan Johansen Feb 13 at 18:10
16
\$\begingroup\$

JavaScript (Node.js), 144 138 125 74 73 70 bytes

f=(x,n=2,c=0)=>x%n?x-!c?f(x,n+1)/(n%4>2?n/=~c&1:n%4)**c:1:f(x/n,n,c+1)

Try it online!

-4 byte thanks @Arnauld!

Original approach, 125 bytes

a=>(F=(x,n=2)=>n*n>x?[x,0]:x%n?F(x,n+1):[n,...F(x/n,n)])(a).map(y=>r-y?(z*=[,1,.5,p%2?0:1/r][r%4]**p,r=y,p=1):p++,z=r=p=1)&&z

Try it online!

Inspired by the video Pi hiding in prime regularities by 3Blue1Brown.

For each prime factor \$p^n\$ in the factorization of the number, calculate \$f(p^n)\$:

  • If \$n\$ is odd and \$p\equiv 3\text{ (mod 4)}\$ - \$f(p^n)=0\$. Because there is no place to go.
  • If \$n\$ is even and \$p\equiv 3\text{ (mod 4)}\$ - \$f(p^n)=\frac{1}{p^n}\$.
  • If \$p=2\$ - \$f(2^n)=\frac{1}{2^n}\$.
  • If \$p\equiv 1\text{ (mod 4)}\$ - \$f(p^n)=1\$.

Multiply all those function values, there we are.

Update

Thanks to the effort of contributors from Math.SE, the algorithm is now backed by a proof

\$\endgroup\$
  • \$\begingroup\$ Does the video contain a proof? I've been trying to prove this result for a few hours now but I couldn't figure it out. \$\endgroup\$ – infmagic2047 Feb 11 at 3:38
  • 1
    \$\begingroup\$ @infmagic2047 Not really, but it gives a method to count the number of points on a \$\sqrt{n}\$ circle. This is useful when coming down to how the n-mover can go. \$\endgroup\$ – Shieru Asakoto Feb 11 at 3:39
  • 3
    \$\begingroup\$ @infmagic2047 I think it's trivial to prove the cases for \$q=\prod_{p\in\mathbb{P}\land p\in\{2,3\}\text{ (mod 4)}}p^{e_p}\$ but the cases for the remaining ones are quite hard to prove formally... \$\endgroup\$ – Shieru Asakoto Feb 11 at 11:30
  • 1
    \$\begingroup\$ @infmagic2047 's math.se question about this approach now has an answer with a complete proof. \$\endgroup\$ – Ørjan Johansen Feb 13 at 18:09
11
\$\begingroup\$

Clean, 189 185 172 171 bytes

import StdEnv
$n#r=[~n..n]
#p=[[x,y]\\x<-r,y<-r|x^2+y^2==n]
=sum[1.0\\_<-iter n(\q=removeDup[k\\[a,b]<-[[0,0]:p],[u,v]<-q,k<-[[a+u,b+v]]|all(\e=n>=e&&e>0)k])p]/toReal(n^2)

Try it online!

Finds every position reachable in the n-side-length square cornered on the origin in the first quadrant, then divides by n^2 to get the portion of all cells reachable.

This works because:

  • The entire reachable plane can be considered as overlapping copies of this n-side-length square, each cornered on a reachable point from the origin as if it were the origin.
  • All movements come in groups of four with signs ++ +- -+ --, allowing the overlapping tiling to be extended through the other three quadrants by mirroring and rotation.
\$\endgroup\$
  • \$\begingroup\$ My apologies - I was looking at the test cases which go from N=10 to N=13, whereas your test cases include N=11 and N=12 too. You are indeed correct for N=13. +1 from me :) \$\endgroup\$ – trichoplax Feb 11 at 0:51
  • 1
    \$\begingroup\$ @trichoplax I've changed the tests to correspond to the question to avoid the same confusion again \$\endgroup\$ – Οurous Feb 11 at 0:53
  • \$\begingroup\$ I've further tested up to N=145 and all are correct. I couldn't test 146 on TIO due to the 60 second timeout though. I'm expecting some very long run times in answers here... \$\endgroup\$ – trichoplax Feb 11 at 1:01
  • 1
    \$\begingroup\$ Since I took a while to realize this: The reason why the square corners are reachable if there is at least one move (a,b), is the complex equation (a+bi)(a-bi)=a^2+b^2, which in vector form becomes (N,0)=a(a,b)+b(b,-a). \$\endgroup\$ – Ørjan Johansen Feb 11 at 17:19
8
\$\begingroup\$

Mathematica, 80 bytes

d[n_]:=If[#=={},0,1/Det@LatticeReduce@#]&@Select[Tuples[Range[-n,n],2],#.#==n&];

This code is mostly reliant on a mathematical theorem. The basic idea is that the code asks for the density of a lattice given some generating set.

More precisely, we are given some collection of vectors - namely, those whose length squared is N - and asked to compute the density of the set of possible sums of these vectors, compared to all integer vectors. The math at play is that we can always find two vectors (and their opposite) that "generate" (i.e. whose sums are) the same set as the original collection. LatticeReduce does exactly that.

If you have just two vectors, you can imagine drawing an identical parallelogram centered at each reachable point, but whose edge lengths are the given vectors, such that the plane is completely tiled by these parallelograms. (Imagine, for instance, a lattice of "diamond" shapes for n=2). The area of each parallelogram is the determinant of the two generating vectors. The desired proportion of the plane is the reciprocal of this area, since each parallelogram has just one reachable point in it.

The code is a fairly straightforward implementation: Generate the vectors, use LatticeReduce, take the determinant, then take the reciprocal. (It can probably be better golfed, though)

\$\endgroup\$
  • \$\begingroup\$ 76 bytes: d@n_:=Boole[#!={}]/Det@LatticeReduce@#&@Select[Range[-n,n]~Tuples~2,#.#==n&] \$\endgroup\$ – lastresort Feb 11 at 6:00
3
\$\begingroup\$

Jelly,  25  24 bytes

ÆFµ%4,2CḄ:3+2Ịị,*/ʋ÷*/)P

A monadic link using the prime factor route.

Try it online!

How?

ÆFµ%4,2CḄ:3+2Ịị,*/ʋ÷*/)P - Link: integer, n               e.g. 11250
ÆF                       - prime factor, exponent pairs        [[2,1], [3,2], [5,4]]
  µ                   )  - for each pair [F,E]:
    4,2                  -   literal list [4,2]
   %                     -   modulo (vectorises)                [2,1]  [3,0]  [1,0]
       C                 -   complement (1-x)                  [-1,0] [-2,1]  [0,1]
        Ḅ                -   from base 2                         -2     -3      1      
         :3              -   integer divide by three             -1     -1      0
           +2            -   add two (call this v)                1      1      3
                  ʋ      -   last four links as a dyad, f(v, [F,E])
             Ị           -     insignificant? (abs(x)<=1 ? 1 : 0)   1      1      0
                */       -     reduce by exponentiation (i.e. F^E)  2      9     625
               ,         -     pair v with that                   [1,2]  [1,9]  [3,625]
              ị          -     left (Ị) index into right (that)     1      1     625
                    */   -   reduce by exponentiation (i.e. F^E)    2      9     625
                   ÷     -   divide                                1/2    1/9  625/625
                       P - product                                 1/18 = 0.05555555555555555

Previous 25 was:

ŒRp`²S⁼ɗƇ⁸+€`Ẏ;Ɗ%³QƊÐLL÷²

Full program brute forcer; possibly longer code than the prime factor route (I might attempt that later).

Try it online!

Starts by creating single moves as coordinates then repeatedly moves from all reached locations accumulating the results, taking modulo n of each coordinate (to restrict to an n by n quadrant) and keeping those which are distinct until a fixed point is reached; then finally divides the count by n^2

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

05AB1E, 27 26 25 bytes

ÓεNØ©<iozë®4%D≠iyÈ®ymz*]P

Port of @ShieruAsakoto's JavaScript answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

Ó                   # Get all prime exponent's of the (implicit) input's prime factorization
                    #  i.e. 6 → [1,1]      (6 → 2**1 * 3**1)
                    #  i.e. 18 → [1,2]     (18 → 2**1 * 3**2)
                    #  i.e. 20 → [2,0,1]   (20 → 2**2 * 3**0 * 5**1)
                    #  i.e. 25 → [0,0,2]   (25 → 2**0 * 3**0 * 5**2)
 ε                  # Map each value `n` to:
  NØ                #  Get the prime `p` at the map-index
                    #   i.e. map-index=0,1,2,3,4,5 → 2,3,5,7,11,13
    ©               #  Store it in the register (without popping)
     <i             #  If `p` is exactly 2:
       oz           #   Calculate 1/(2**`n`)
                    #    i.e. `n`=0,1,2 → 1,0.5,0.25
      ë             #  Else:
       ®4%          #   Calculate `p` modulo-4
                    #    i.e. `p`=3,5,7,11,13 → 3,1,3,3,1
          D         #   Duplicate the result (the 1 if the following check is falsey)
           ≠i       #   If `p` modulo-4 is NOT 1 (in which case it is 3):
             yÈ     #    Check if `n` is even (1 if truthy; 0 if falsey)
                    #     i.e. `n`=0,1,2,3,4 → 1,0,1,0,1
             ®ymz   #    Calculate 1/(`p`**`n`)
                    #     i.e. `p`=3 & `n`=2 → 0.1111111111111111 (1/9)
                    #     i.e. `p`=7 & `n`=1 → 0.14285714285714285 (1/7)
              *     #    Multiply both with each other
                    #     i.e. 1 * 0.1111111111111111 → 0.1111111111111111
                    #     i.e. 0 * 0.14285714285714285 → 0
 ]                  # Close both if-statements and the map
                    #  i.e. [1,1] → [0.5,0.0]
                    #  i.e. [1,2] → [0.5,0.1111111111111111]
                    #  i.e. [2,0,1] → [0.25,1.0,1]
                    #  i.e. [0,0,2] → [1.0,1.0,1]
  P                 # Take the product of all mapped values
                    #  i.e. [0.5,0.0] → 0.0
                    #  i.e. [0.5,0.1111111111111111] → 0.05555555555555555
                    #  i.e. [0.25,1.0,1] → 0.25
                    #  i.e. [1.0,1.0,1] → 1.0
                    # (and output implicitly as result)
\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 126 bytes

.+
$*
+`^(11+)(\1)+\b
$1;1$#2$*
\b1(1111)+\b
1
\b(1(11)+);\1\b
$1_$1
.*\b(1(11)+)\b.*
0
_
;
+`\G1(?=.*;(1+))|;1+$
$1
11+
1/$.&

Try it online! Link includes test cases. Uses the prime factorisation. Explanation:

.+
$*

Convert to unary.

+`^(11+)(\1)+\b
$1;1$#2$*

Get the prime factors.

\b1(1111)+\b
1

Delete factors of the form 4k+1.

\b(1(11)+);\1\b
$1_$1

Temporarily mark any duplicate pairs of remaining odd factors (i.e. of the form 4k+3).

.*\b(1(11)+)\b.*
0

If there are any unmatched odd factors remaining then the result is zero.

_
;

Remove the markings.

+`\G1(?=.*;(1+))|;1+$
$1

Multiply any remaining factors back together. (Taken from the Unary arithmetic tutorial.)

11+
1/$.&

Compute the reciprocal as a decimal fraction.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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