Circles and prime numbers

[Ynaught?]

Some time ago I began playing around with packing circles and I have some questions that I am hoping someone here can help with.

I have linked to three PDF files that should help in understanding my synopsis below. (You will need to click on the blank sheet and then open the PDF’s as I am not sure how to link to them directly – sorry for the inconvenience.)

http://cid-64f8d3658ef4ddc3.skydrive.live.com/self.aspx/Public/The%20Whole%20Picture.pdf"

http://cid-64f8d3658ef4ddc3.skydrive.live.com/self.aspx/Public/The%20Center.pdf"

http://cid-64f8d3658ef4ddc3.skydrive.live.com/self.aspx/Public/The%20Pattern.pdf"

In “The Whole Picture” the background is a lattice of hexagonically packed unit circles. The “center” unit circle is arbitrarily selected. From the center circle, circumferential circles are drawn, each 2 times the unit circle diameter greater than the next. By constructing circumferential circles is such a manner, there are a minimum of six unit circles in each successive hexagonal packing that are internally tangential to the circumferential circle associated with that packing. So, from the center circle (packing q=0) the first packing (q=1) contains six circles that are internally tangential to a circumferential circle that has a radius of 3 (unit circle has a radius of one). The second packing (q=2) contains an additional six circles that are internally tangential to a circumferential circle that has a radius of 5. In the “The Center” drawing linked above, you can see that these six unit circles at every packing level are at 60, 120,180, 240, 300, and 360 degrees. Since the centers of these circles form the vertices of the hexagon representative of the associated packing, I have elected not to identify them in any special way.

Now, whenever the hexagonal packing level equals a prime number of the form 6n+1, there are 12 additional circles that are internally tangential to the associated concentric circles. In the drawings linked above, these are represented by green shading. Additionally, all multiples of that prime also include 12 additional internally tangential unit circles. These multiple occurrences are represented by magenta shading. For example, at q=7, there are twelve internally tangential circles, shaded green and at q=14, 21, 28… the unit circles are shaded magenta. “The Pattern” has the background of unit and concentric circles turned off.

Notice that only when 6n+1 is prime are additional unit circles tangential to the associated concentric circle. So 7, 13, 19, 31… have additional circles but not 25, 49 (except as a multiple of 7), 55, 85…

Also, when the packing level equals the multiple of two non identical primes of the form 6n+1, there are 36 additional unit circles that are internally tangential to the associated concentric circle. These are represented in the drawing by cyan shading and are shown at 91 (7*13) and 133 (7*19).

The drawings referenced are taken out to only 144 packing level.

All that to get to my questions… :)

1) Why do the internally tangential unit circles only appear at primes (and multiples thereof) of the form 6n+1 and not primes of the form 6n-1?
2) Why do the internally tangential unit circles only appear at primes (and multiples thereof) of the form 6n+1 and not all packing levels 6n+1?
3) If you imagine the center of each unit circle of the background as forming a grid, is there a way to determine the angle of the internally tangential circles associated with a packing level, based on whole number steps of that grid?

Mahalo!

 

[wawa63]

Circles and diophantian equation

Hi,

Well, I've no answer to your questions but I've studied your problem and have some hints to give to you. Yet, I'm french and I beg your pardon if my english is sometime poor.

1- Translation to a diophantian equation
Let's take a circle as origin $$O$$ - as you did. Every circle $$C$$ can be associated with two integers $$(n,p)$$, so that there would be, from $$O$$ to $$C$$, $$n$$ right/left steps and $$p$$ steps in the complex direction $$\frac{1}{2}+i\frac{\sqrt{3}}{2}$$.

Equivalently, $$C$$ can be associated with the complex number

$$n+p\times(\frac{1}{2}+i\frac{\sqrt{3}}{2})=(n+p/2)+ip\frac{\sqrt{3}}{2}$$

Now, a circle is internally tangential to the circumferential circle if and only if the distance between its center and $$O$$ is an integer, i.e. if and only if :

$$(n+p/2)^2+p^2\frac{3}{4}=q^2$$

for an integer $$q$$ which can be interpreted as your hexagonal packing level. It leads to the diophantian equation :

$$n^2+p^2+n\times p=q^2$$

2- Symetries
Obviously, the solutions are invariant by a rotation around $$O$$ with angle $$\pi/3$$. So that if $$(n,p,q)$$ is a solution, so are $$(-p,n+p,q)$$, $$(-n-p,n,q)$$, $$(-n,-p,q)$$, $$(p,-n-p,q)$$ and $$(n+p,-n,q)$$.

The vertices of the hexagon representative of the associated packing

are for example associated with the solutions $$(n,0,n)$$ and by the symetries given above $$(0,n,n)$$, $$(-n,n,n)$$, $$(-n,0,n)$$, $$(0,-n,n)$$ and $$(n,-n,n)$$.

This means that we can consider that $$n>0$$ and $$p>0$$ as we already know the trivial solutions corresponding to the hexagonal vertices and as the other solutions can be deduced by symetry.

As we also can exchange $$n$$ and $$p$$, we also can consider that $$n\geq p$$.

See next post for the continuation ;-)

 

[wawa63]

Circles and diophantian equation - 2

3- Solution of the diophantian equation
The diophantian equation

$$n^2+p^2+n\times p=q^2$$ (1)

can be written :

$$p^2+n\times p=q^2-n^2$$ conducting to $$p(n+p)=(q+n)(q-n)$$ (2)

We try to solve it with $$(n,p,q)$$ relatively primes, i.e. such that no integer divide two of them. Indeed, if $$a$$ divides, let's say, $$n$$ and $$q$$ then, as $$p^2=q^2-n^2-n\times p$$
$$a$$ must divide $$p$$, and divides all of them.

Let's define $$u=q+n$$ and $$v=q-n$$. Equation (2) can be rewritten :

$$p(\frac{u-v}{2}+p)=uv$$ (3)

Now, equation (1) yields to $$(n+p)^2-np=q^2$$ so that $$n+p>q$$ and $$p>v$$ so that $$p$$ can't divide $$v$$. But $$p$$ could be composite, $$p=bc$$, with $$b$$ dividing $$v$$ and $$c$$ dividing $$u$$.
I assume that it is not the case and that $$p$$ must divide $$u$$. Yet, I can't prove it right now.

Anyway, let's assume that $$p$$ and $$v$$ are relatively prime (***). Then equation (3) allows us to write $$u=pw$$ and becomes :

$$pw-v+2p=2vw$$ which yields to $$p(w+2)=v(2w+1)$$ (4)

As we assumed, $$p$$ and $$v$$ are relatively prime. If it's true, we can again write $$1+2w=rp$$ or $$w=\frac{rp-1}{2}$$ and (4) rewrites :

$$\frac{rp-1}{2}+2=rv$$ which yields to $$r(2v-p)=3$$ (5)

So that either $$r=3$$ and $$2v=p+1$$ (6)
or $$r=1$$ and $$2v=p+3$$ (7)

Now, injecting backwards (6) and (7), we have 2 cases :
o either $$r=3$$ and $$p=2v-1$$
$$w=3v-2$$
$$u=(2v-1)(3v-2)$$
$$n=\frac{u-v}{2}=3v^2-4v+1$$
$$q=\frac{u+v}{2}=3v^2-3v+1$$

o or $$r=1$$ and $$p=2v-3$$
$$w=v-2$$
$$u=(2v-3)(v-2)$$
$$n=v^2-4v+3$$
$$q=v^2-3v+3$$Injecting this in (1), we can verify that this two cases give effective solutions to our diophantian equation, for every integer value of $$v$$. Yet, we could miss some solutions, because I didn't prove (***).

I bet that (***) is true. If it is, then all relatively primes $$(n,p,q)$$ are of the form above. The other non-trivial solutions can be found by multiplying those by an integer $$m$$ : $$(mn,mp,mq)$$.

EDIT : (***) is false. First counter-example : n=95 p=24 q=109. The formulaes above miss some solutions.

4- Solutions given for $$r=1$$

v=0 p=-3 n=3 q=3
v=1 p=-1 n=0 q=1
v=2 p=1 n=-1 q=1
v=3 p=3 n=0 q=3
v=4 p=5 n=3 q=7
v=5 p=7 n=8 q=13
v=6 p=9 n=15 q=21
v=7 p=11 n=24 q=31
v=8 p=13 n=35 q=43
v=9 p=15 n=48 q=66
v=10 p=17 n=63 q=73

 

[wawa63]

Circles and diophantian equation - 3

5- Actual relatively primes solutions and values of parameters

n=5 ; p=3 ; q=7 >>> u=12 ; v=2 ; w=4 >>> r=3
n=8 ; p=7 ; q=13 >>> u=21 ; v=5 ; w=3 >>> r=1
n=16 ; p=5 ; q=19 >>> u=35 ; v=3 ; w=7 >>> r=3
n=24 ; p=11 ; q=31 >>> u=55 ; v=7 ; w=5 >>> r=1
n=33 ; p=7 ; q=37 >>> u=70 ; v=4 ; w=10 >>> r=3
n=35 ; p=13 ; q=43 >>> u=78 ; v=8 ; w=6 >>> r=1

 

[wawa63]

Definitive formula

Ok, here's a formula which gives all non-trivial solutions $$(n,p,q)$$. The demonstration of this formula is almost the same as the demonstration above, but it takes into account the cases for which $$n+q$$ and $$p$$ are not relatively primes.

First, chose two integers $$a$$ and $$b$$ such that :
1- either they are both odd, or they are both even ;
2- $$GCD(a,b)$$ is 1 or 2.

Then the non-trivial solutions have one of the 2 following forms :

$$r=1$$
$$n=\frac{a^2-2ab-3b^2}{4}$$
$$p=ab$$
$$q=\frac{a^2+3b^2}{4}$$

$$r=3$$
$$n=\frac{3a^2-2ab-b^2}{4}$$
$$p=ab$$
$$q=\frac{3a^2+b^2}{4}$$

Examples :
r=1 a=5 b=1 >> n=3 p=5 q=7 Green
r=1 a=7 b=1 >> n=8 p=7 q=13 Green
r=1 a=12 b=2 >> n=21 p=24 q=39 Purple

r=3 a=5 b=1 >> n=16 p=5 q=19 Green
r=3 a=7 b=1 >> n=33 p=7 q=37 Green
r=3 a=12 b=2 >> n=95 p=24 q=109 Green

The answers to your questions remain not clear for me.

 

[Ynaught?]

Hey wawa63,

Thank you! You didn't answer the questions but gave me lots to chew on. One quick follow on question regarding symmetries (I am sure more will follow when I have more time):

Since n and p are the complex portion of the coordinates and since pi/6 is normal to the side of the hexagon, can we assume n is the mirror of p and then just work within a pi/6 slice instead of a pi/3 slice?

(BTW, I find your French to English translation much better than my English to Math <LOL>)

-mahalo

 

[Ynaught?]

A second quick follow up...

Regarding

First, chose two integers a and b such that :
1- either they are both odd, or they are both even ;
2- GCD (a,b) is 1 or 2.

The odds seem to be working well, but I quickly run into problems with the evens.

Example:

r=1, a=6, b=2 >> n=0, p=12, q=12
r=1, a=10, b=2 >> n=12, p=20, q=28

Is there a specific reason why 1. cannot read, "a and b are both odd"?

 

[wawa63]

Hi Ynaught,

Yes, we can work in a pi/6 slice as if (n,p,q) is a solution, so is (p,n,q). But remarkabily, I don't use the symetries in the solution of the diophantian equation. I first thought I would need it, and then realized it wasn't the case.

Yet, a solution using symetries would probably be more powerful and beautiful.

For your second remark, I don't see problems with the examples you give : they are solutions of the equation, even if they aren't relatively prime solutions - let's call them "primitive solutions". The formulas I gave are necessary but not sufficient for a solution to be a "primitive solution". Therefore, some solutions aren't primitive. And yet, we need the "a and b both even", for example in this case :
r=3 a=12 b=2 >> n=95 p=24 q=109 Green

 

[Ynaught?]

Hey wawa63,

And yet, we need the "a and b both even"

Are you certain? We can take this route to 109 as well...

r=1, a=19, b=5 >> n=24, p=95, q=109 Green

I am curious to see if the formulas can be tweaked to only allow primative solutions. The first step would be to get rid of the even a's and b's... So by saying that the solution (either n or p) is the one that is less than 1/2 of q (invoking the symmetry), could we drop the even inputs?

 

[wawa63]

Well, you're right, I should work on this further to be able to get only solutions
1. that are primitive
2. that fall in a pi/6 slice, let's say for example n>0, p>0 and n>p.
The title of my fourth post should be "A (not so) definitive formula" ;-)

I won't have time to do this until sunday. I will post whenever I will find something interesting.
By the way, I think your assumptions and questions about the fact that for primitive solutions q is a prime of the form 6k+1 are very interesting. Although I don't see why it should be true, I'm guessing you're right.

I'm wondering if a number theorician could help you (us ;-) on this. Is it a result already known ? I don't think so, but in fact, I don't know...

 

[dodo]

Just a bystander observation:

A quick number-crunching shows that, for q=91, there are multiple (n,p) pairs (11,85), (19,80), (39,65), (49,56) that are solutions of n^2 + np + p^2 = q^2; and thus their rotations and reflexions, for a total of 48 instead of 12 circles in that level.

A similar phenomenon repeats for other q values. Up to q <= 200, they are (I think):
q=49; (16,39), (21,35)
q=98; (32,78), (42,70)
q=133; (23,120), (35,112), (57,95), (65,88)
q=147; (48,117), (63,105)
q=169; (15,161), (91,104)
q=182; (22,170), (38,160), (78,130), (98,112)
q=196; (64,156), (84,140)

Edit: the OP accounts for cases with 48 circles, like q=91, yet (I think) not for cases like q=49 with 24 circles each. I can but wonder if higher q values will show even more circles.

Edit, next morning: Oh, yes, for example q=637 has the 7 solutions (77,595), (133,560), (145,552), (200,513), (208,507), (273,455), (343,392).

 

[Ynaught?]

Hey wawa63 and welcome Dodo,

wawa63: Take your time, I look forward to seeing what you find.

Dodo: How did you calaulate your (n,p) pairs for each q? I am curious how you did your "quick number-crunching?" I think it may help with finding primative solutions.

Mahalo!

 

[dodo]

Hi, Ynaught?,
it's something I googled, rather than something I know.

n^2 + np + p^2 = q^2 is, in real numbers, the equation of a (rotated) ellipse. Now, any ellipse, rotated or not, has a leftmost and a rightmost (single) point. If you solve for, say, p, and get p = (-n +/- sqrt (4q^2 - 3n^2)) / 2, you will get two solutions for n values "inside" the ellipse, and just one p value for the extremes, where the sqrt=0. At these extremes, 4q^2 = 3n^2, giving you n = +/- q . 2/3 . sqrt (3). This gives you the range for n. So I did a program that iterates for integer values of n from 1 to q . 2/3 . sqrt (3), and then (1) determines if 4q^2 - 3n^2 is a perfect square, and if it is, (2) checks if the value of p (using the + alternative of the +/- in the formula for p) is an integer > 0, that is, if sqrt(4q^2 - 3n^2) - n is a positive even.

Hope this helps. By the way, your 6n+1 conjecture seems right up to q values of 10000. All q values for which there is a solution have at least one prime factor congruent to 1 (mod 6).

I wonder, for a rectangular (not hexagonal) grid, is there a similar 4n+1 conjecture? In this case, the diophantine equation would be simply n^2 + p^2 = q^2, the most famous solution being for q=5, (3,4). Are there other numbers, other than 4 and 6, around which a grid of circles can also be organized?

 

[Ynaught?]

Hey Dodo and wawa63,

I guess an ellipse makes some since wawa63 translated $$1/2 + \sqrt{}3/2$$ to get an integer count... Hopefully he will explain further.

I was curious about your method of finding each (n,p,q) because, in doing so, you filled a hole that had been bugging me for a while. It did not make sense that the additional tangential circles should increase from 12 to 48 (skipping over 24). But I did not notice the occurrence of (16,39,49) until you pointed it out. Since 49 is 7*7, there should be an extra tangential circle, in addition to the one duplicate at (21,35,49). Likewise, (32,78,98) and (42,70,98) are doublings of the (n.p,q) at q = 49. Keep on adding multiples of 7… How many do you get for q=343?

The statement in the OP should now read:
“When the packing level equals multiples of two primes of the form 6k+1:
1. There are 12 additional internally tangential unit circles when the primes are identical.
2. There are 36 additional internally tangential unit circles when the primes are not identical, etc...”

So, since q=637 is 7^2*13, it suggests to me that there should be eight (n,p) multiples (two pair for the 7^2 and four pair for the non identical primes). Either you missed one or my reasoning is off… Any ideas?

Regardless, by iterating it seems to me that if we ignore all solutions that provide more that one set of (n,p) we end up with a set of primitive solutions.

With regard to a rectangular lattice, it sounds like you are asking about Pythagorean Primes and Pythagorean Triples…

 

[Ynaught?]

Hey Dodo,

I forgot to say thanks for checking on values up to 10000. Thanks.

I think the conjecture that all q with valid solutions have at least one prime factor is true as well and I like the way you worded it. But, like wawa63, I don't see any reason why. Maybe a number theoretician will step in with some guidance. In the mean time, I am looking forward to see if he can find equations that provide solutions,

1. that are primitive
2. that fall in a pi/6 slice, let's say for example n>0, p>0 and n>p.

In the mean time, and in an effort to see why valid solutions q are NOT primes of the form 6k-1 (or 4k+1), I was wondering about a pentagonal lattice instead of a rectangular one... I have not thought about Pythagorean Triples in a long time. 4k+1 on a rectangular lattice gives the same answers (but for different values of k), yes? I know the conjecture, "All primes, greater than 3, are of the form 6k +or- 1" is proven. Therefore, is the conjecture, "All primes, greater that 3 are of the form 4k+1 or 6k+1" also true?"

11 is prime and there is no integer k that produces 11 with 4k+1. That was a quick, “No”.

So what about 5k+1… “No” again, can’t reach 13…

It therefore seems logical to look for 6k-1. The question is then, “On which lattice do we look?”

-Mahalo

 

[dodo]

For q=343 I get the three solutions (37,323), (112,273), (147,245). In the attachment at the bottom of this post, I am including the C source code for hexagonal and rectangular grids, as well as the results I get up to 10000. (Please don't use the programs too much beyond 10000, since at a certain point the results are garbled due to numerical overflow.)

I think the conjecture that all q with valid solutions have at least one prime factor is true as well and I like the way you worded it.

Actually I only worded half of the conjecture, the "if" part. As for the other half (the "only if"), "only primes of the form 6k+1 (and their multiples) produce additional circles", it seems also true up to 10000. I used the 'factor' command in Linux to factorize numbers and, up to 10000, the list of primes of the form 6k+1 plus their multiples exactly coincides with the list of q values in solutions of the diophantine equation. I also checked, up to 10000, the analogue for rectangular grids: the list of 4k+1 primes plus multiples exactly coincides with the list of values of q in solutions.

"All primes, greater that 3 are of the form 4k+1 or 6k+1"

As you noticed, this is not true. The reason why all primes greater than 3 are either 6k+1 or 6k+5 (which is the same as 6m-1, for k=m-1) is because the other possibilities for residues modulo 6, namely 6k, 6k+2, 6k+3 and 6k+4, are divisible resp. by 6, 2, 3 and 2, so they cannot be primes. For the '4' case, a similar statement would be "all primes above 2 are of the form 4k+1 or 4k+3 (= 4m-1)", since the possibilities 4k and 4k+2 are clearly composite. The example you mention, 11, is of the form 4k-1.

When googling about Pythagorean primes, I see, in this Wolfram's Mathworld page,
http://mathworld.wolfram.com/DiophantineEquation2ndPowers.html
around equation (13), that the conjecture for rectangular grids (the "if" part, at least) seems to be a fact, yet I have still to understand the reasons given in that page ("every prime of the form 4x+1 can be expressed as the sum of two relatively prime squares"). I wouldn't be surprised if your conjecture can also be proven true by one of the number theoreticians around.

And I don't see how to form a pentagonal grid, without getting spacing holes between the circles. They won't fit all tangentially to each other, it seems to me.

 

[Ynaught?]

Hey Dodo,

For q=49 I had found the (21,35) as the 7th recurrence of the (3,5) pair but had not noticed the (16,39) pair. Interestingly, wawa63’s formulas give the (16,39) solution (at r=1, a=13, b=3) but it does not give a solution for (21,35).

For q=343, his formulas gives solutions (37,323) and (147,245) but not (112,273). (37,323) is obliviously new and (147,245) is the 49th recurrence of the (3,5) pair. This time, the missing solution is the 7th recurrence of the (16,39) pair, namely (112,273).

The formulas seem to “hide” the 7th recurrence of a prime q…

Looking again at q=637, the formulas find solutions for (145,552) and (200,513) but not:
(77,595) is the 7th recurrence of (11,85) q=91
(133,560) is the 7th recurrence of (19,80) q=91
(273,455) is the 7th recurrence of (39,65) q=91
(343,392) is the 7th recurrence of (49,56) q=91
(208,507) is not a 7th recurrence of anything. But it is the 13th recurrence of (16,39) q=49.

Looking at values for q of 49, 91, 343, and 637, the number of pairs associated with any non prime q seem to equal g*h+ (f-g+h), where f = the factors of q, g = the number of prime factors of q, and h = the number of uniquely prime factors of q. As a result, q=4459 should include 10 pairs and q=8281 should include 11 pairs. Your attachment is still “pending approval” so I can’t compare these figures to your data yet.

Up to 10000, the list of primes of the form 6k+1 plus their multiples exactly coincides with the list of q values in solutions of the diophantine equation.

is promising… With not so much data and no proof, I have been leery of the “only if” part. But your program provides two orders of magnitude more data than I started with. ;) Is “10000”, q= 10,000 or the set of q within the first 10,000 integers?

Also, I must admit, that I am a bit confused on the differences between 6k+/-1 and 4k+/-1. If I understanding correctly, neither the Pythagorean solution nor this hexagonal one provide solutions for “Xk-1”. I realize that a pentagonal lattice in a Euclidian plane leaves gaps. I was wondering if there was a way to project a pentagonal packing into a 2d plane similarly to the way the PDF files linked in the OP project the complex (n,p) pairs into a 2d hexagonal plane. IIRC, the “n” is the x direction and the “p” is the y (complex) direction, and “q” is the radius of the circle. The single complex coordinate (n,p) is represented by two different points (unit circles) in the lattice. If my understanding is correct, I am wondering if anyone has any ideas on how to do the same thing and get Xk-1 solutions. If my understanding is incorrect, please show me how.

Mahalo

 

[dodo]

Hi,
sorry that the attachment is still pending. The results I get for 4459 are 10: (481,4199), (539,4165), (931,3920), (1015,3864), (1400,3591), (1456,3549), (1911,3185), (1965,3139), (2325,2816), (2401,2744). But for 8281 I get actually 12: (735,7889), (1001,7735), (1729,7280), (1885,7176), (1991,7104), (2600,6669), (2704,6591), (2856,6475), (3401,6039), (3549,5915), (4221,5320), (4459,5096). The limit of 10000 refers to the maximum value of q searched, not to the total number of solutions.

I'm not sure I understand what you mean by "the Nth recurrence of ...". In any case, I did some more testing: the solutions can be filtered to the primitive ones only, just by checking gcd(n,p)=1. (It's easy to see that gcd(n,q)=1 and gcd(p,q)=1 follow as a consequence, both for the equation n^2 + np + p^2 = q^2 of the hexagonal case, as for the n^2 + p+2 = q^2 of the rectangular case.) On primitive solutions, all prime factors, not just some, of each value of q <= 10000 are of the form 6k+1 (or 4k+1 for the rectangular grid). However, they are not necessarily powers of the same prime: f.i. q=1729 appears, which factors to 7 * 13 * 19.

In the rectangular case, Pythagorean triples are studied in the Hardy & Wright book of number theory (which I had obviously not read up to page 190): theorem 225 proves the Euclid construction, taking u,v as positive coprimes, u>v, such that one is even and the other is not, and setting n=2uv, p=u^2-v^2, q=u^2+v^2 (and inverting n and p when necessary if you need n<p). With this construction is easy, using arithmetic modulo 4, to prove that q has to be of the form 4k+1; but as for all its prime factors being of that form, I am in the dark.

 

[Ynaught?]

The Nth recurrence... n^2 + np + p^2 = q^2 produces:

1. A pair of coordinates (n,p) for every 6k+1 prime (q).

2. A pair of coordinates for each non-prime solution that has only one 6k+1 prime factor. For example: (6,10,14), (9,15,21), (12,18,28), … Sequenced multiples of (3,5,7).

3. Multiple sets of pair of coordinates for non-prime solutions that have more than one 6k+1 prime factors.

Some of the multiple sets of the non-prime solutions are recurrences and others are not. The pairs that are recurrent are identified as such if n and p are divisible by at least one of the prime factors in q. For example, the two pairs in q=49 are (21,35) and (16,39). 21=7^3 and 35=7^5.

So alternately stated, what I am calling a recurrence is the powers to which the prime roots are raised in each pair.

I know that much of my wording does not adhere to convention, so feel free to correct me when I err. ;)

 

[dodo]

You might find this interesting. It applies to Pythagorean triples, but the behavior seems similar to the one you observe for the hexagonal grid.
http://www.math.rutgers.edu/~erowland/pythagoreantriples.html
If you scroll down to "III. Counting triples", it says that the number of primitive solutions for a certain q is always a power of two, depending on how many distinct prime factors q has (no matter the power of those factors) of the form 4k+1; if there are k such factors, there will be 2^(k-1) primitive solutions with that q. All factors must have that form; if one doesn't, q does not belong to a primitive solution.

As examples for the hexagonal case (where this seems to verify for q <= 10000), q=49 has only one primitive solution because 49=7^2, but q=91 has two primitive solutions because 91=7*13. The first with four primitive solutions is q=1729=7*13*19, namely (96,1679), (249,1591), (656,1305), (799,1185).

The same argument appears at
http://mathworld.wolfram.com/PythagoreanTriple.html
Scroll down to equations (23) and (24).

 

[Ynaught?]

Hey Dodo,

Thanks for the code, data and links! From what I can tell, 2^(n-1), where n is the number of distinct prime factors of the form 6k+1 hold for the hexagonal case as well. In addition to the solutions I could look up in your data, I ran through q=53599 (with 4 distinct 6k+1 prime factors) through wawa63’s solutions and found 8 primitive pairs.

r=1, a=463, b=3 >> n=52891, p=1389
r=3, a=267, b=23 >> n=50264, p=6141
r=1, a=461, b=25 >> n=46899, p=11525
r=1, a=457, b=43 >> n=41000, p=19651
r=1, a=265, b=61 >> n=43656, p=16165
r=3, a=263, b=83 >> n=39240, p=21829
r=1, a=439, b=85 >> n=24104, p=37315
r=3, a=255, b=139 >> n=2616, p=35445
(There are two additional r=3 solution but they give the inverse of n and p of the first two above).

I guess it’s time to read up on my ancient Greeks. A few posts back I asked wawa63 what he thought about dropping the evens a’ and b’s (analogous to the u and v in the rectangular case with the Hardy & Wright book). And since,

theorem 225 proves the Euclid construction, taking u,v as positive coprimes, u>v, such that one is even and the other is not, and setting n=2uv, p=u^2-v^2, q=u^2+v^2 (and inverting n and p when necessary if you need n<p). With this construction is easy, using arithmetic modulo 4, to prove that q has to be of the form 4k+1

it would seem that there should be no problem with relying on the pi/3 symmetry.

Mahalo

 

[dodo]

Hi, Ynaught?,
I've been working on some theory bits for generating primitive integer solutions of n^2 + np + p^2 = q^2. I still have to prove a lot of things (I have only done implications on one direction, not on the other), and work more on constraining the values to avoid negative integers or repeated solutions, but so far it looks promising. (I'll write down here all formal derivations for this when I finish.)

It would go this way:
Choose positive integers s,t such that
- gcd(s,t)=1
- they are of opposite parity (one even and the other odd)
- s is not divisible by 3
At least one of them will not be divisible by 3 (3 can't divide both, otherwise gcd(s,t) would be at least 3), so exchange s and t as needed.

Now, from these s,t,
- Set g=s^2, h=3t^2. Exchange g and h if needed, so that g>h (They can't be g=h, since sqrt(3) is irrational.)
- Set e=g+h, a=g-h, v=(st)/2, u=e-7v
- And finally set n=u-v, p=(a-n)/2, q=u+v

And voila, solutions galore. (For the moment, reject negatives n,p,q; I'm working on bringing restrictions down to s and t.) (Also, repeated solutions appear for n,p both odd. I'm working on it.)

Sample output, after filtering out negative n,p,q and sorting by q:

      s      t      g      h      u      v      n      p      q
      -      -      -      -      -      -      -      -      -
      4      1     16      3      5      2      3      5      7
      1      2     12      1      6      1      3      5      7
      2      3     27      4     10      3      7      8     13
      7      2     49     12     12      7      5     16     19
      4      5     75     16     21     10     11     24     31
     10      3    100     27     22     15      7     33     37
      1      4     48      1     35      2      7     33     37
      8      1     64      3     39      4     13     35     43
      5      6    108     25     28     15     13     35     43
      2      5     75      4     44      5     16     39     49
     13      4    169     48     35     26      9     56     61
     11      2    121     12     56     11     32     45     67
     10      1    100      3     68      5     17     63     73
      7      8    192     49     45     28     17     63     73
      4      7    147     16     65     14     40     51     79
     16      5    256     75     51     40     11     85     91
      1      6    108      1     88      3     11     85     91
      8      9    243     64     55     36     19     80     91
     14      3    196     27     76     21     55     57     97
      5      8    192     25     77     20     55     57     97

 

[Ynaught?]

Hey Dodo,

Excellent stuff! I look forward to seeing the results.

Something you may find interesting. I have been looking at the symmetry around pi/6 and I do not know why I did not see this before, but the third of my questions in the OP has an answer...

When one uses the diophantine equation n^2+2np+p^2=q^2 and generates primitive solutions for (n,p,q) where n<p<q and then translates (n,p,q) onto a rectangular background such that n is the base of a triangle, p is its height, and the angle at the vertex of n and p equals 2/3pi the hypotenuse will equal q.

-Mahalo

 

[bucky77015]

Though I haven't studied in any depth the equations given as replies, by reading your initial post and the responses you've received, it looks as though you're looking for an approximation of the diameter of a minimum enclosing circle for a circle packing of n-unit circles?! If this is the case then please disregard the following comments. Although, if you're looking for an exact solution, please read on.

A hexagonal or "honeycomb" packing is the most efficient method of packing circles while a minimum enclosing circle is in reality a horrible choice. Yet, it has many applications in various fields. The main problem that I see is when you say that each successive packing simply adds 2d to the diameter of the preceding packing. This is incorrect; although I will not tell you why. Not to be mean but I've been at this forever & I'd like to come to my own conclusion.