Given a circle
x^2+y^2=r^2
Evaluate the number of points with integer coordinates ( both x and y ) inside the circle ( i.e. points within the area enclosed by the curve)
Assuming r itself is an integer:
clearvars
for r=1:100
ct=0; ctExact=0;
for x=1:r
y=sqrt(r^2-x^2);
ct=ct+floor(y)+1;
if y==ceil(y)
ct=ct-1;
ctExact=ctExact+1;
end
end
ct=4*ct+1;
ctExact=4*ctExact;
fprintf('%5d %10d %9d %10d\n',r,ct,ctExact,ct+ctExact)
end
finds
points
internal exactly on total
r points circle
1 1 4 5
2 9 4 13
3 25 4 29
4 45 4 49
5 69 12 81
6 109 4 113
7 145 4 149
8 193 4 197
9 249 4 253
10 305 12 317
11 373 4 377
12 437 4 441
13 517 12 529
14 609 4 613
15 697 12 709
16 793 4 797
17 889 12 901
18 1005 4 1009
19 1125 4 1129
20 1245 12 1257
21 1369 4 1373
22 1513 4 1517
23 1649 4 1653
24 1789 4 1793
25 1941 20 1961
26 2109 12 2121
27 2285 4 2289
28 2449 4 2453
29 2617 12 2629
30 2809 12 2821
31 2997 4 3001
32 3205 4 3209
33 3405 4 3409
34 3613 12 3625
35 3841 12 3853
36 4049 4 4053
37 4281 12 4293
38 4509 4 4513
39 4765 12 4777
40 5013 12 5025
41 5249 12 5261
42 5521 4 5525
43 5785 4 5789
44 6073 4 6077
45 6349 12 6361
46 6621 4 6625
47 6917 4 6921
48 7209 4 7213
49 7521 4 7525
50 7825 20 7845
51 8161 12 8173
52 8485 12 8497
53 8797 12 8809
54 9141 4 9145
55 9465 12 9477
56 9841 4 9845
57 10185 4 10189
58 10545 12 10557
59 10909 4 10913
60 11277 12 11289
61 11669 12 11681
62 12057 4 12061
63 12449 4 12453
64 12849 4 12853
65 13237 36 13273
66 13669 4 13673
67 14069 4 14073
68 14493 12 14505
69 14945 4 14949
70 15361 12 15373
71 15809 4 15813
72 16237 4 16241
73 16717 12 16729
74 17181 12 17193
75 17645 20 17665
76 18121 4 18125
77 18601 4 18605
78 19097 12 19109
79 19573 4 19577
80 20069 12 20081
81 20589 4 20593
82 21089 12 21101
83 21625 4 21629
84 22129 4 22133
85 22665 36 22701
86 23213 4 23217
87 23757 12 23769
88 24309 4 24313
89 24833 12 24845
90 25433 12 25445
91 25985 12 25997
92 26561 4 26565
93 27141 4 27145
94 27725 4 27729
95 28333 12 28345
96 28913 4 28917
97 29513 12 29525
98 30145 4 30149
99 30753 4 30757
100 31397 20 31417
The "points exactly on circle" correspond to pythagorean triples of x, y and r, or the ndpoints of the four radii.
OEIS sequences are A051132 and A000328 for the internal and total columns respectively
For the former, no formula is given in the OEIS.
For the latter, a formula is given:
a(n) = 1 + 4 * Sum_{j>=0} floor(n^2/(4*j+1)) - floor(n^2/(4*j+3))
Verifying the formula (which counts the points exactly on the circle):
% a(n) = 1 + 4 * Sum_{j>=0} floor(n^2/(4*j+1)) - floor(n^2/(4*j+3))
n=r; s=0;
for j=0:n^2
s=s+floor(n^2/(4*j+1)) - floor(n^2/(4*j+3));
end
byFormula=1+4*s;
fprintf('%5d %10d %9d %10d %10d\n',r,ct,ctExact,ct+ctExact,byFormula)
But the formula is really no more closed-form than my algorithm.
total formula
= A000328
1 1 4 5 5
2 9 4 13 13
3 25 4 29 29
4 45 4 49 49
5 69 12 81 81
6 109 4 113 113
7 145 4 149 149
8 193 4 197 197
9 249 4 253 253
10 305 12 317 317
11 373 4 377 377
12 437 4 441 441
13 517 12 529 529
14 609 4 613 613
15 697 12 709 709
16 793 4 797 797
17 889 12 901 901
18 1005 4 1009 1009
19 1125 4 1129 1129
20 1245 12 1257 1257
21 1369 4 1373 1373
22 1513 4 1517 1517
23 1649 4 1653 1653
24 1789 4 1793 1793
25 1941 20 1961 1961
26 2109 12 2121 2121
27 2285 4 2289 2289
28 2449 4 2453 2453
29 2617 12 2629 2629
30 2809 12 2821 2821
31 2997 4 3001 3001
32 3205 4 3209 3209
33 3405 4 3409 3409
34 3613 12 3625 3625
35 3841 12 3853 3853
36 4049 4 4053 4053
37 4281 12 4293 4293
38 4509 4 4513 4513
39 4765 12 4777 4777
40 5013 12 5025 5025
41 5249 12 5261 5261
42 5521 4 5525 5525
43 5785 4 5789 5789
44 6073 4 6077 6077
45 6349 12 6361 6361
46 6621 4 6625 6625
47 6917 4 6921 6921
48 7209 4 7213 7213
49 7521 4 7525 7525
50 7825 20 7845 7845
51 8161 12 8173 8173
52 8485 12 8497 8497
53 8797 12 8809 8809
54 9141 4 9145 9145
55 9465 12 9477 9477
56 9841 4 9845 9845
57 10185 4 10189 10189
58 10545 12 10557 10557
59 10909 4 10913 10913
60 11277 12 11289 11289
61 11669 12 11681 11681
62 12057 4 12061 12061
63 12449 4 12453 12453
64 12849 4 12853 12853
65 13237 36 13273 13273
66 13669 4 13673 13673
67 14069 4 14073 14073
68 14493 12 14505 14505
69 14945 4 14949 14949
70 15361 12 15373 15373
71 15809 4 15813 15813
72 16237 4 16241 16241
73 16717 12 16729 16729
74 17181 12 17193 17193
75 17645 20 17665 17665
76 18121 4 18125 18125
77 18601 4 18605 18605
78 19097 12 19109 19109
79 19573 4 19577 19577
80 20069 12 20081 20081
81 20589 4 20593 20593
82 21089 12 21101 21101
83 21625 4 21629 21629
84 22129 4 22133 22133
85 22665 36 22701 22701
86 23213 4 23217 23217
87 23757 12 23769 23769
88 24309 4 24313 24313
89 24833 12 24845 24845
90 25433 12 25445 25445
91 25985 12 25997 25997
92 26561 4 26565 26565
93 27141 4 27145 27145
94 27725 4 27729 27729
95 28333 12 28345 28345
96 28913 4 28917 28917
97 29513 12 29525 29525
98 30145 4 30149 30149
99 30753 4 30757 30757
100 31397 20 31417 31417
|
|
Posted by Charlie
on 2023-06-12 12:59:14 |
for integral r only (spoiler)
