just want to let everyone know that i figured it out, it was actually very simple to prove that the number of squares that the boundary of a circle with radius r, centered on the center of one of the tiles passes over is exactly 8*r for all r.
>>7909759
What if the tile size changed
>>7909786
Axiom of choice.
>>7909759
OK, where's your proof?
>tfw pi=9
>>7910015
Where is it anon? I'm curious
>>7909759
what happen if the circle pass through a corner ? 4 squares touched ? or maybe not possible because pi?
>>7910148
This is easily possible if you allow any real radius.
>>7909759
OP has posted something interesting. Let's brainstorm about how to express such an arrangement, and how to go about proving OP's claim.
Off the top of my head, I would begin with the Cartesian plane, and imagine the circles of natural radius which emanate from the origin, but I don't even want to express those just yet. Instead, I want to consider the "nicest" possible way to partition R^2 in the way that OP's problem requires. For this, rather than working with squares of unit edge length which partition the plane, I propose instead to work with squares which have edge lengths of 2. This will allow us to equivalently partition the plane in nice integer/natural number terms, without mucking around with any fractions. We would then double our circles in like fashion, so that we consider the circles of radius 2, 4, 6, etc.
We also have to decide how space is partitioned, and what it means for a circle to cut, touch, include a particular square. A touch of an edge or a corner (without just cutting through two adjacent squares without any tangency) would constitute inclusion, but my spidey-sense tells me that some cases of this are impossible.
So I would start like this. R^2 is partitioned into squares, which are demarcated by the lines
[math] \displaystyle x = j [/math]
[math] \displaystyle y = n [/math]
with odd n and j.
[cont]
>>7910277
[cont]
The corners which are common to four squares, are precisely the lattice points which have both components odd: (-3, 5), (1,-1), (7,9) etc. (0,3) and (-5,2) are not such lattice points. The open line segments which are common to some two squares, are those segments so bounded by our above corners. The open interior of a given square is of course unique to that square. So in the course of setting up the problem, I am interested in these three regions of the plane.
Now, with respect to the above, define a semi-radius 2q = r , and state the problem (in as many words): how many of the above square regions of space are touched by the circles emanating from the origin, having even radii, s.t.
[math] \displaystyle x^2 + y^2 = 4q^2 = r^2 [/math]
for natural q, and equivalently even r ?
>>7910281
Inelegant Remark (since I'm still thinking about terminology I'd prefer to use): Each such circle obviously includes a quartet of points which are the x-y intercepts. Moreover, each such circle's four such points are obviously strictly inside the open interior sectors of four different (disjoint) open squares, so that later we may say that the squares which each such circle passes through, obviously /includes/ those four disjoint squares.
To find these points, variously set x or y equal to zero, and extract a square root. we have four cases giving rise to four points (-r,0), (r,0), (0,-r), (0,r). But r is always even, so that when q = 1, the implicated open squares are themselves disjoint, (and only spread further and further apart for larger circles).
So, these circles each obviously touches four distinct lattice points. But in another sense, we are not concerned with these, but instead with the odd lattice points which I described above. Do any of these circles touch one of those odd lattice points? I think not, and I think that I can show this by using the negation of Euclid's formula (which always requires an odd hypotenuse in primitive triangles, but I need to think about this):
https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple
>>7910342
Let's continue this train of thought a bit by aping the above wiki, and reviewing what pythagorean triples are, and why they're pertinent to the above train of thought. Maybe we get a lemma out of this.
A pythagorean triple is a solution of the /Diophantine/ equation
[math] x^2 + y^2 = r^2 [/math]
, and per Euclid's formula and its above derivation (very important to understanding this), the /primitive/ triples (having coprime legs) have one leg even, and one odd, giving rise to an odd hypotenuse. This says nothing about which of the two legs is longer (it may be either even or odd). Now, the primitive Pythagorean triples generate /all/ Pythagorean triples upon integer multiplication, over all integers (or natural numbers, for our discussion). A primitive triple has parity (this is a fancy word from number theory to denote whether given numbers are even or odd) "oeo", which upon applying an odd multiplier returns "oeo". Odd-times-odd is odd, etc. And, of course, upon applying an even multiplier, becomes "eee". But we require that our hypotenuse, or radius r, is even. And the above three cases are exhaustive of Pythagorean triples, in general. And therefore, in my above development/rephrase of OP's problem, The only lattice points which may rest on one of the circles of even radius which we investigate, are those which correspond to non-primitive Pythagorean triples in which all three component are even numbers.
I'm not the smartest, but I don't see how OP's finding is interesting in any way. Also, I'm interested in the cases where it would pass through a corner (intersection of four adjacent tiles) instead of intersecting a single tile. Would the principle still work?
doesnt work for circles with non integer radii
Let's consider the smallest pertinent example of what I'm talking about. It's time to slow down a bit and draw nice pictures. Coincidentally, this is a nice illustrative continuation of OP's graphic.
The smallest Pythagorean triple is (3,4,5), which upon the smallest available even multiplication (doubling) returns (6,8,10). We thus require that r = 10, or OP's radius (q) = 5.
The colored lines and green point are the axes/origin, while the standard mesh of black lines represents the odd line and odd lattice points, not to be confused with the GENERAL lattice points. Since in my terms our radius is even, the only pythagorean triples, or so to say GENERAL lattice points which may rest on this particular circle, have even components, and so do not touch any of the ODD lattice points (corners of the black lines) , which is what I'm investigating. I've inserted in light gray markers of the general integer lattice at the pertinent spots where the circle does in fact intersect the points (+-6, +-8)...(+-8, +-6). I just added in the red line to look fancy and be a visual aid.
The drawing's lack of precision makes it look like maybe the circle touches the isosceles points (+-7,+-7). Obviously this doesn't actually happen since 98 is slightly less than 100. Furthermore, the appropriate "squares" can be included, and counted off.
And OP's pattern holds good. when q = 5, the number of squares cut by the circle is 8q, or 40.
>>7910648
no it wouldnt work. the principle doesnt work for circles with non integer radii.
>>7910735
Then just restrict the problem to natural radii then and brainstorm that.
>>7910756
yeah just clarifying
>>7910736
And now that I've thought about this a bit, I can express my lemma.
Question: Do the circles described in the thread ever touch any CORNER points of their associated lattice? In my treatment, do the circles ever include the ODD lattice points, which require that both of their components is odd?
Answer (lemma): no.
Proof: By Euclid's formula, and how ALL Pythagorean triples are generated (primitives per Euclid's formula, complemented by all multiples of primitives), we require that all Pythagorean triples have either parity "oeo", or "eee". And, since the pertinent radius is always even, the former case is discarded. What is left is that a given circle with even radius may intersect non-primitive triples, both of whose components are even. (an example was recently given, for illustration). But these points, quite the opposite of being corner points of our lattice, are instead center points of the open squares described above. Moreover, the question above should require that the pertinent triangle have a parity of "ooe", which by Euclid's formula is impossible - one of the two legs of a Pythagorean triple is ALWAYS even. We therefore conclude that the circles described in the thread never touch any corner points in the associated lattice.
>>7910763
Much easier lemma, after a moment's thought:
Do any of the thread's circles ever lie tangent to one of the lines that describe the lattice? No. For these lines only face in one of two directions, orthogonal to each other, and not densely. Therefore, in order for a circle to lay tangent to one of them, we should require that its radius is odd, which is not how OP has set up our inquiry (as I've re-developed it in my own terms). We conclude that a circle with even radius never lays tangent to any one of the lines of the lattice.
And, more generally, since we have eliminated both such possibilities, we see that the thread's circles only ever cut /through/ the lattice's lines, continuously into the open interiors of the lattice's described open squares, which are to be counted.
>>7910648
Just disproved that as a possibility buddy, where the circle's radii increment relative to same lattice.
Happily, the above two lemmas coalesce into a nice small theorem, which has already been stated. The concerns that I earlier had about how to "count" tangent lattice lines, points, etc, are therefore happily rendered superfluous in this problem. The other anon who pointed out the related Gauss circle problem >>7910733
is also to be commended.
So now that the point-line-issue is banished, we can just assume (because it's been proven true) that OP's circles only ever cut through squares, and their bodies. Another concrete treatment of this (pic related) shows how consecutive circles tend to share certain squares, and even how larger circles require more complex linear combinations of certain squares.
And for all this, in lieu of running extensive internet searches, I've been thinking for myself (with the help of some established theorems) on some related issues and sticking points. And yet I don't yet know how to prove OP's claim, nor has he himself furnished a proof. This is therefore left to us as an exercise.
Induction? Some incrementing geometric argument? As I can already see, there are low-number cases where shared blocks are "skipped", or otherwise tripled-up.
Perhaps a given radius "scanning" through a given quadrant is a right approach, since we no longer have to worry about hitting ODD lattice points.
>>7909759
Con fucking gratis Pythagoras II
OP here, great to see someone else interested in this.
since having the circle tangent to a boundary, or crossing a corner has already been shown to not be an issue (>>7910763) ill just give my reasoning continuing from >>7910923
that the squares are 8*r.
Looking at a single quadrant, lets say the positive x-y one, the circle is monotonic decreasing. as you follow the circle from (0,r) you can cross into a new square in 2 ways, either to the right, or to the bottom of the previous one. The endpoint of the circle (in that quadrant) is at (r,0). also, ill only count one of the squares centered on (0,r) or (r,0) so that the number of squares in total is 4 * the number in 1 quadrant.
Since you can only move to a new square to the right or bottom of the old one, this is actually a problem in the taxicab metric. The distance between these 2 points in this metric is |r-0| + |r-0| = 2r.
Multiply this by 4 for each quadrant and it 8*r
>>7912021
So maybe there's some result about equivalence of two metrics that I don't know. Because we go straight from 2r to 8r (the quadrant thing makes sense, I'm just missing steps).
However, I can see a version of this. Never taking the axial points (missing information), I spray-paint out some cab rides, corresponding to the circles and also to your thing in a sense. Counter-clockwise, we have paths of length 4, 8, 12, 16, and 20, which are just double my even radii, or double your radii, as you said. But I've assumed traveling strictly along the exterior just to match your model, yet this doesn't sound right (because I've intentionally left out the information of the intercept-blocks!)
>>7909759
Thanks, actually. This is very useful for providing a way to calculate how much material I'll need for Minecraft constructions involving circles.
This is equivalent to proving primitive Pythagorean triples cannot have two odd legs. This is easy.
>>7909759
I never thought about it but seems like youre right
every time the radius is increased by 1, it moves 1 in all 4 directions. and each direction adds 2 new squares because the line has to move in that direction and then move back
from what I can tell is it does not even have to be a circle. it just has to be confined in the square of side length s=1+2*r, reach at least 1 square touching each side and only be allowed to bend in 1 direction (so no moving back and forth to hit more squares). then it is obvious that it hits as many squares as there are border tiles (s1->1, s2->4, s3-> 8, sn -> (n-1)*4 --> rn->n*8)
then the only problem is when the line goes exactly through the corner of a square. each time that happens it technically dodges 1 square. then all there is to do is test if and how frequently during increasingly large circles this special thing happens
but for that I am too lazy right now because that would require actual math
>>7912499
well I forgot to write two things
first, there is an other problem, when the line goes along the border of a square. second, the number depends on how you count these special cases. all bordering squares? none of them?
>>7912499
>then the only problem is when the line goes exactly through the corner of a square.
This can't occur since it would require a right triangle with sides r, a+0.5, b+0.5 with r, a, and b integers and this is impossible.
>>7912560
nice, doing it with mod is smart
good job
>>7912571
well, actually I am retarded
you dont even need mod to know this wont happen
all you need to do is look at the fucking triangle and its obvious
damn I am so stupid
>>7912579
It's not that obvious that primitive Pythagorean triples must have one odd leg and one even leg.
>>7912586
>primitive Pythagorean triples
ahh so that's what they're called!
thank you for the help!
>>7909759
Does it work for other values of pi as well?
