Count squares in my pi approximation

Question

One way to approximate π is the following: Start by drawing a 2x2 square with a quarter-circle in it. Then, the area of the quarter-circle is π.

We can approximate this area by filling it with squares. To start, we divide the square into four squares. Only one of these is fully inside the circle, so we colour it in and get a value of π = 1.

Next, we repeat the same thing with the other three squares, dividing them into quarters and colouring those fully contained in the quarter-circle. This gives a value of π = 2.

And again, with π = 41/16 ≈ 2.56:

And again, with π = 183/64 ≈ 2.86:

Once more, with π = 385/128 ≈ 3.007:

And one last time, because these are pretty, with π = 3149/1024 ≈ 3.075:

Your challenge is to count the squares in each iteration of this pattern. The first pattern has one red square (total 1), then the next pattern has four orange squares for a total of 5, then the next has nine yellow squares for a total of 14, and so on. The sequence continues 1, 5, 14, 33, 71, 140, 274, 563, 1083... - here's an example python program to calculate the first few terms.

While this specific sequence is not on OEIS, its variations A156790 and A177144 are. (incidentally, this is what you get if you search the first few terms of the sequence). Standard sequence I/O rules apply - you may take a 0/1-indexed n and output the nth / first nterms, or just output the whole sequence indefinitely.

This is code-golf, shortest wins!

Interesting challenge, but of course, it's equivalent to Monte - Carlo integration of that curve, which is a traditional "toy" method for calculating pi. (If you aren't familiar with it throw random darts at the one by one square, count the ratio which fall within or outside one unit of the origin, derive area of that quarter circle from that ratio. Accuracy is limited by the quality of your random number generator, the number of digits your calculations can be carried out to, and how long you are willing to repeat the experiment while waiting for the result to stabilize. Common homework!) — keshlam, Commented Sep 17 at 17:35

David Chew · Accepted Answer · 2024-09-17 12:39:27Z

7

Python 3, 100 93 83 bytes

lambda m:sum((4**n-i*i)**.5//1*(n//m*4-3)for n in range(m+1)for i in range(1,2**n))

(Old: Try it online!)

-7 bytes thanks to emanresuA: Try it online!

-10 bytes thanks to GB and emanresuA: Try it online!

(Old: f calculates A156790 and the first lambda function takes the sum of the first n terms of A177144.)

Same as old, but f is combined with g by using a double for loop and (n//m*4-3), which in this context is 1 only for n==m and -3 otherwise.

edited Sep 17 at 12:39

answered Sep 17 at 0:01

David Chew

2411 silver badge7 bronze badges

3

\$\begingroup\$ You don't need to calculate the g= since it's not referred to within the code (TIO) \$\endgroup\$
– emanresu A
Commented Sep 17 at 3:16
2

\$\begingroup\$ Pretty much, yeah. We accept anonymous functions here as long as they're not tied to any specific name - e.g. lambda a,b: a + b, this is just a more general form of that. You'll also see e.g. lambda a,b: re.sub(r'\d+', a, b); import re. Having the anonymous function be at the start is just for convenience to allow binding it to a variable to not have to be in the code block. \$\endgroup\$
– emanresu A
Commented Sep 17 at 5:40
2

\$\begingroup\$ Here is 89 with even smarter non-recursive tricks :-) \$\endgroup\$
– G B
Commented Sep 17 at 10:40
2

\$\begingroup\$ Based on G B's, 84 by merging the for comprehensions \$\endgroup\$
– emanresu A
Commented Sep 17 at 11:03
2

\$\begingroup\$ Actually 83 \$\endgroup\$
– emanresu A
Commented Sep 17 at 11:07

| Show 3 more comments

138 Aspen · Accepted Answer · 2024-09-17 02:31:41Z

Scala 3, 173 169 bytes

Saved 4 bytes thanks to @Unrelated String

Golfed version. Attempt This Online!

val p=BigInt(2).pow
def f(n:Int)=(1to p(n).toInt-1).map(i=>math.floor(math.sqrt((p(2*n)-BigInt(i).pow(2)).toDouble)).toLong).sum
def g(n:Int)=f(n)-3*(0to n-1).map(f).sum

Ungolfed version. Attempt This Online!

object Main {
  def main(args: Array[String]): Unit = {
    for (i <- 0 to 20) {
      val result = g(i)
      println(s"g($i) = $result")
    }
  }

  def f(n: Int): Long = {
    var total = 0L
    val maxValue = BigInt(2).pow(2 * n)  // Equivalent to 4^n
    val limit = BigInt(2).pow(n).toInt   // Upper limit for i in the range
    for (i <- 1 until limit) {
      val diff = maxValue - BigInt(i).pow(2)
      val sqrtValue = math.sqrt(diff.toDouble)
      total += math.floor(sqrtValue).toLong
    }
    total
  }

  def g(n: Int): Long = {
    val sumPreviousF = (0 until n).map(f).sum
    f(n) - 3 * sumPreviousF
  }
}

ref Python code

def f(n):
    """
    Computes the sum over i from 1 to (2^n - 1) of the floor of sqrt(4^n - i^2).

    This function calculates the total integer parts of the square roots of (4^n - i^2)
    for each integer i in the range from 1 to 2^n - 1.
    """
    total = 0
    max_value = 2 ** (2 * n)  # This is 4^n, since 4^n = (2^n)^2
    limit = 2 ** n  # The upper limit of the range for i

    for i in range(1, limit):
        # Calculate the square root of (4^n - i^2)
        sqrt_value = (max_value - i * i) ** 0.5
        # Add the floor of the square root to the total sum
        total += int(sqrt_value // 1)
    return total

def g(n):
    """
    Computes the adjusted value g(n) by subtracting three times the sum of f(i) for i from 0 to n-1 from f(n).

    This function effectively isolates the new contributions at each level of n by removing
    overlapping counts from previous levels.
    """
    sum_previous_f = sum(f(i) for i in range(n))  # Sum of f(i) for all i from 0 to n-1
    return f(n) - 3 * sum_previous_f

# Compute and print g(n) for n from 0 to 20
for i in range(21):
    result = g(i)
    print(f"g({i}) = {result}")

I see you already caught some of the unnecessary whitespace, but you can also get rid of the whitespace between literals and to as well as some redundant parentheses. Also, val p=BigInt(2).pow saves another 4. — Unrelated String, Commented Sep 17 at 2:31

G B · Accepted Answer · 2024-09-17 10:13:01Z

4

Ruby, 93 ... 69 bytes

->n{-3*(1..n).sum{|x|n=(1..2**x).sum{|i|((4**x-i*i)**0.5).to_i}}+n*4}

Try it online!

Using the same approach as @David Chew in his Python solution, avoiding recursion makes it shorter and faster.

edited Sep 17 at 10:13

answered Sep 17 at 8:44

G B

22.7k1 gold badge20 silver badges53 bronze badges

Add a comment |

Kjetil S · Accepted Answer · 2024-09-20 10:22:04Z

Perl 5.10, 173 132 bytes

@c=[2,$l=2];while($l/=2){@c=grep$$_[0]**2+$$_[1]**2<4?$n++*0:1,map{($x,$y)=@$_;[$x,$y],[$x-$l,$y],[$x-$l,$y-$l],[$x,$y-$l]}@c;say$n}

Try it online!

...outputs 1, 5, 14, 33, 71, 140, 274, 563, 1083, 2159, 4293, 8391 before it times out after one minute.

@c = ( [ 2, 2 ] );                 #starting top right corner
$l = 2;                            #starting length
while( $l /= 2 ){                  #reduce length by half each round
  @c =                             #new corners for next round
    grep $$_[0]**2 + $$_[1]**2 < 4 #pyt dude
         ? $n++ * 0                #count up if inside circle, dont keep corner
         : 1,                      #keep corner, but dont count up
    map {                          #for each current corner...
      ($x,$y) = @$_;               #...split current square into four:
      (
        [ $x,    $y    ],
        [ $x-$l, $y    ],
        [ $x-$l, $y-$l ],
        [ $x,    $y-$l ]
      )
    }
    @c;                            #current corners
  say $n                           #output count each round
}

Unrelated String · Accepted Answer · 2024-09-17 15:49:37Z

Jelly, 16 bytes

4*p`ḋ`<Ɗ)§Äṫ-ḅ-4

Try it online!

VERY slow--times out for n=6, brute forcing \$16^6 = 2^{24}\$ calculations.

  p`        For every pair of numbers from
4*          [1 .. 4^n],
    ḋ`      is its dot product with itself (sum of squares)
      <Ɗ    less than 4^n?

See below for further explanation:

Jelly, 18 17 bytes

4*Æ²Ƈạ$)½Ḟ§Äṫ-ḅ-4

Try it online!

-1 thanks to Jonathan Allan

Takes n as input and outputs the nth element, computing the sequence as the cumulative sums of A177144 (number of squares added to areas not covered by squares in the previous iteration of A156790). Just barely beats the first-n-outputting 4*Æ²Ƈạ$)½Ḟ§×4ạḊƲÄṖ and the somewhat faster R2*R²ạ²Ʋ€½Ḟ§Äṫ-ḅ-4.

       )             For each m in [1 .. n],
          §          sum
        ½            the square roots
         Ḟ           floored
4*   ạ               of 4^n minus
  Æ²Ƈ $              every perfect square less than or equal to it.
            ṫ-       Last two
           Ä         cumulative sums
              ḅ-4    converted from base -4.

4*Æ²Ƈạ$)½Ḟ§ḋṬo-3Ɗ and a few variants thereof tie, borrowing a little mathematical manipulation from David Chew's Python solution. Likewise 4*ṖṚÆ²T)½Ḟ§Äṫ-ḅ-4. A faster 16 sounds almost possible.

...Come to think of it, 2*R²ạ²Ʋ)½Ḟ§Äṫ-ḅ-4 also ties. Not sure how I missed that one, but I still like the suggested version too :P

Jelly, 37 bytes

2*R²ạ²Ʋ½ḞBUz0s"J’2*Ʋ$Ṛ_ṂḤŒHƲ€Ẏ+ɗ\ẎṂ€S

Try it online!

Utterly hopeless, but too fun an idea to pass up :P

Uses the binary expansion of each row to represent greedily filling it with powers of 2, then merges or explodes said powers of 2 into appropriate squares.

Jelly, 31 bytes

U»\U)
2*R²ạ²Ʋ½Rọ2Ç2*«ZgJ€ƲÇFİ²S

Try it online!

Hacked together to try to do it graphically. Miraculously seems to work.

Slower, but save one with 4*Æ²Ƈạ$)½Ḟ§Äṫ-ḅ-4 TIO (Keep perfect squares up to \$4^n\$ and "subtract" each from \$4^n\$.) — Jonathan Allan, Commented Sep 17 at 13:20

138 Aspen · Accepted Answer · 2024-09-17 02:52:58Z

2

Wolfram Language (Mathematica), 125 bytes

use quick floorSqrt from this answer.

Try it online!

s@n_:=Floor[Sqrt[SetPrecision[n,RealExponent[1.001n]/2]]]
f@n_:=Sum[s[(4^n-i^2)],{i,1,2^n-1}]
g@n_:=f@n-3*Sum[f[i],{i,0,n-1}]

edited Sep 17 at 2:52

answered Sep 17 at 2:47

138 Aspen

6,4391 gold badge4 silver badges13 bronze badges

Add a comment |

The Empty String Photographer · Accepted Answer · 2024-09-17 18:53:09Z

Python 3, 176 bytes

x=a=0;y=1
while 1:x*=4;z=len([*filter(lambda x:x[0]**2+x[1]**2<4,(lambda i:[(x*i,y*i)for x in range(1,int(2/i+1))for y in range(1,int(2/i+1))])(y))])-x;a+=z;print(a);y/=2;x+=z;

Try it online!

Outputs the sequence infinitely.

x and a are initialized to \$0\$, and y is initialized to \$1\$.

It does this next paragraph forever:

It multiplies x by 4. It then creates a list of the possible top-right corners of the squares with size y, then removes the vertices which do not satisfy the condition \$x^2+y^2<4\$. It sets z to the number of vertices which haven't been removed. minus x from it. z is added to a. It prints the current value of a, and then divides y by \$2\$, and adds z to x.

Jake · Accepted Answer · 2024-09-18 05:23:35Z

2

Javascript (Node.JS), 121 114 69 bytes

Versions:
Original: Try it online!
Version 2 (-7 bytes): (Thanks to emanresu) Try it online!
Version 3, with Recursion sorcery (-45 bytes) Try it online!

g=n=>n&&(F=(m,i=1<<m)=>i&&F(m,i-1)+(4**m-i*i)**.5|0)(n)+g(--n)-4*F(n)

edited Sep 18 at 5:23

answered Sep 17 at 2:18

Jake

3161 silver badge7 bronze badges

\$\begingroup\$ Since we allow anonymous function submissions on this site (as long as they don't refer to themselves) you don't have to count the g=. Also, you can save a few more bytes by using **.5 instead of Math.sqrt - Try it online! \$\endgroup\$
– emanresu A
Commented Sep 17 at 5:47
3

\$\begingroup\$ That said, with a lot of recursive shenaniganry here's 69 bytes, which does require counting the g= because it's recursive \$\endgroup\$
– emanresu A
Commented Sep 17 at 5:58

Add a comment |

emanresu A · Accepted Answer · 2024-09-17 21:42:25Z

1

Vyxal, 16 bytes

ƛEDẊ²Ṡ√>∑;¦÷$4*ε

Try it Online!

Mostly a port of UnrelatedString's Jelly answer. ~~There's got to be a way to save a byte on the last bit~~ -1 thanks to UnrelatedString.

ƛ        ;       # Over 1...n
        ∑        # Count the number of 
  DẊ             # Pairs
 E               # Of 1...2^m
    ²Ṡ√          # Whose squared sums, sqrt'd
       >         # Are less than
 E               # 2^m
          ¦      # Take the cumulative sum
           ÷   ε # Subtract from the last item
            $4*  # The second-to-last item times 4

edited Sep 17 at 21:42

answered Sep 17 at 20:33

emanresu A

43.8k5 gold badges100 silver badges239 bronze badges

\$\begingroup\$ ÷$4*ε seems to save one byte on the last bit \$\endgroup\$
– Unrelated String
Commented Sep 17 at 21:31
\$\begingroup\$ @UnrelatedString Nice, thanks! \$\endgroup\$
– emanresu A
Commented Sep 17 at 21:41

Add a comment |

Neil · Accepted Answer · 2024-09-18 04:39:11Z

Charcoal, 35 bytes

ＩΣＥＸ²⮌…·¹Ｎ×ΣＥιΣＥι‹⁺Ｘ⊕λ²Ｘ⊕ν²Ｘι²∨¬κ±³

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

    ²                               Literal integer `2`
   Ｘ                                Vectorised raised to power
      …·                            Inclusive range from
        ¹                           Literal integer `1` to
         Ｎ                          Input as an integer
     ⮌                              Reversed
  Ｅ                                 Map over values
             ι                      Current value
            Ｅ                       Map over implicit range
                ι                   Current value
               Ｅ                    Map over implicit range
                     λ              Inner value
                    ⊕               Incremented
                   Ｘ                Raised to power
                      ²             Literal integer `2`
                  ⁺                 Plus
                         ν          Innermost value
                        ⊕           Incremented
                       Ｘ            Raised to power
                          ²         Literal integer `2`
                 ‹                  Is less than
                            ι       Current value
                           Ｘ        Raised to power
                             ²      Literal integer `2`
              Σ                     Take the sum
           Σ                        Take the sum
          ×                         Multiplied by
                                κ   Current index
                               ¬    Is zero
                              ∨     Logical Or
                                  ³ Literal integer `3`
                                 ±  Negated
 Σ                                  Take the sum
Ｉ                                   Cast to string
                                    Implicitly print

I tried a more "graphical" version but it came out to be 56 54 bytes:

≔Ｘ²Ｎθ⊞υＥ³θＦυ¿›ΣＸ…ι²¦²Ｘθ²«≔÷⌊ι²η¿ηＦ⁴⊞υＥι⎇＆κＸ²μλ⁻λη»Ｍ→Ｉⅈ

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

≔Ｘ²Ｎθ

Take 2 to the power of the input.

⊞υＥ³θＦυ

Construct a square of that size and loop over squares are they are generated.

¿›ΣＸ…ι²¦²Ｘθ²«

If this square does not fit inside the circle, then...

≔÷⌊ι²η¿η

Halve the size of the square; if the square still has a size, then...

Ｆ⁴⊞υＥι⎇＆κＸ²μλ⁻λη

... push the four quarters of the original square to be checked.

»Ｍ→Ｉⅈ

Output the total number of squares found.

akamayu · Accepted Answer · 2024-09-18 17:11:06Z

APL (Dyalog Extended), 31 30 bytes

A train that takes \$n\$ as input and outputs the \$n\$th term.

(⊢⌿-1⊥3×1↓⌽)2{≢⍸⍵>|∘.⌾⍨⍳⍵}¨⍤*⍳


             {≢⍸⍵>|∘.⌾⍨⍳⍵}     ⍝ Number of points resides in the first quarter

            2             ¨⍤*⍳ ⍝ For radius of r in [1, 2, 4, 8, 16, ..., 2^n]

(⊢⌿-1⊥3×1↓⌽)                   ⍝ The last one minus three times of the sum of the rest

Let \$G_i\$ be the number of integer grid points that reside in the first quarter of a circle with radius of \$2^i\$ unit. (Not on the circle, nor on the axis.) Then the sequence \$ S \$ can be written as \$ S_i = \sum_{j=0}^i G_j-4G_{j-1} = G_i - 3\sum_{j=0}^{i-1}G_j\$. Since in the \$i\$th level, \$ 4G_{i-1} \$ of squares within \$ G_i \$ were already covered by levels \$j<i\$.

Try it online!

Try it online! 31 bytes

APL(Dyalog Unicode), 38 33 bytes ^SBCS

(⊢⌿-1⊥3×1↓⌽)2(≢∘⍸×⍨>⍳∘.+⍨⍤×⍳)¨⍤*⍳

(⊢⌿-1⊥3×1↓⌽)2(≢∘⍸×>∘.+⍨⍤×⍥⍳)⍨¨⍤*⍳

Try it on APLgolf!

Try it on APLgolf! 38 bytes

\$\begingroup\$ I think I forgot to buy the train ticket. Sorry. \$\endgroup\$
– The Empty String Photographer
Commented Sep 18 at 16:57 — The Empty String Photographer, Commented Sep 18 at 16:57

Stack Exchange Network

Count squares in my pi approximation

11 Answers 11

Python 3, 100 93 83 bytes

Scala 3, 173 169 bytes

Ruby, 93 ... 69 bytes

Perl 5.10, 173 132 bytes

Jelly, 16 bytes

Jelly, 18 17 bytes

Jelly, 37 bytes

Jelly, 31 bytes

Wolfram Language (Mathematica), 125 bytes

Python 3, 176 bytes

Javascript (Node.JS), 121 114 69 bytes

Vyxal, 16 bytes

Charcoal, 35 bytes

APL (Dyalog Extended), 31 30 bytes

APL(Dyalog Unicode), 38 33 bytes ^SBCS

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
integer
pi
or ask your own question.

Hot Network Questions

Count squares in my pi approximation

11 Answers 11

Python 3, 100 93 83 bytes

Scala 3, 173 169 bytes

Ruby, 93 ... 69 bytes

Perl 5.10, 173 132 bytes

Jelly, 16 bytes

Jelly, 18 17 bytes

Jelly, 37 bytes

Jelly, 31 bytes

Wolfram Language (Mathematica), 125 bytes

Python 3, 176 bytes

Javascript (Node.JS), 121 114 69 bytes

Vyxal, 16 bytes

Charcoal, 35 bytes

APL (Dyalog Extended), 31 30 bytes

APL(Dyalog Unicode), 38 33 bytes SBCS

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

Related

Hot Network Questions

APL(Dyalog Unicode), 38 33 bytes ^SBCS

Not the answer you're looking for? Browse other questions tagged
code-golf
sequence
integer
pi
or ask your own question.