等分正方形边长形成的交点数和区域数

iseemu2009

aimisiyou 发表于 2025-4-15 08:30
暴力搜

代码发出来看看

iseemu2009

正方形边长3等分形成的交点数和区域数

mathe

A331449给到了52项为止，我这里继续计算了几项
53 59861345
54 60326225
55 66755641
56 69570973
57 77778357
58 84328717
59 92613453
60 89439969

iseemu2009

mathe 发表于 2025-4-15 16:52
A331449给到了52项为止，我这里继续计算了几项
53 59861345
54 60326225

问题的关键是确定内部某个交点最多可由几条线段相交构成，这个对区域数的形成有绝对影响。对于正n边形，把这n个顶点两两连线，构成众多内部交点，国外大神已经确定无论n为何值，一个交点最多有7条线段相交。

wayne

iseemu2009 发表于 2025-4-15 18:22
问题的关键是确定内部某个交点最多可由几条线段相交构成，这个对区域数的形成有绝对影响。对于正n边形， ...

这个结论是错误的。随便举个例子，比如n=8的时候，过交点为 $(\frac{11}{2},\frac{9}{2})$的直线有8个。分别是下面的直线

{{2,1},{8,7}}
{{2,8},{8,2}}
{{3,1},{8,8}}
{{3,8},{8,1}}
{{4,1},{7,8}}
{{4,8},{7,1}}
{{5,1},{6,8}}
{{5,8},{6,1}}

画的高清矢量图如下：https://nestwhile.com/res/8.pdf。 同颜色的点表示 相交的直线个数相同，直线个数越多，点越大。

1. {1,5,<|1->1|>},
   
2. {2,37,<|6->1,3->8,1->20|>},
   
3. {3,257,<|15->1,6->8,3->32,1->204|>},
   
4. {4,817,<|28->1,15->4,10->8,6->20,3->152,1->616|>},
   
5. {5,2757,<|45->1,15->4,10->16,6->36,3->252,1->2428|>},
   
6. {6,4825,<|66->1,45->4,28->4,21->8,15->16,10->72,6->156,3->572,1->3968|>},
   
7. {7,12293,<|91->1,28->4,21->8,15->16,10->52,6->120,3->900,1->11164|>},
   
8. {8,19241,<|120->1,45->8,36->8,28->8,21->20,15->40,10->132,6->396,3->1712,1->16884|>},
   
9. {9,33549,<|153->1,45->8,36->20,28->8,21->24,15->60,10->140,6->600,3->2536,1->30116|>},
   
10. {10,49577,<|190->1,91->4,55->8,45->8,36->20,28->52,21->56,15->84,10->312,6->948,3->4056,1->43988|>},
    
11. {11,87685,<|231->1,66->4,55->8,45->4,36->4,28->4,21->84,15->48,10->228,6->580,3->4660,1->82016|>},
    
12. {12,101981,<|276->1,153->4,91->24,78->8,45->32,36->32,28->68,21->128,15->424,10->780,6->1840,3->8504,1->90088|>},
    
13. {13,178465,<|325->1,91->4,78->8,66->4,55->4,45->4,36->12,28->52,21->100,15->128,10->396,6->1056,3->8284,1->168360|>},
    
14. {14,220113,<|378->1,153->4,105->8,91->8,78->8,55->4,45->44,36->60,28->140,21->144,15->256,10->924,6->2980,3->13144,1->202332|>}

复制代码

iseemu2009

       我说的是正n边形的情况:当n为奇数时，内部所有交点都由2条线段相交构成，没有其它情况；    当n为偶数时，除中心点外，其它交点最多由7条线段相交构成，这是国外的结论。  本题是正方形每边n等分的情况，结论不同。

mathe

https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=1112
那个问题到那个帖子里讨论吧

mathe

下面这段C++代码，通过修改宏N,就可以计算第N项的结果。

1. #include <iostream>
   
2. #include <map>
   
3. #include <math.h>
   
4. #include <vector>
   
5. #include <gmpxx.h>
   
6. #include <algorithm>
   
7. 
   
8. #ifndef N
   
9. #define N 5
   
10. #endif
    
11. typedef int dtype;
    
12. typedef  long d2type;
    
13. 
    
14. struct Point3{
    
15.         dtype x,y,z;
    
16.         bool operator<(const Point3& p)const{
    
17.                 d2type xm=(d2type)x*p.z, pxm=(d2type)p.x*z;
    
18.                 if(xm!=pxm){
    
19.                         return xm<pxm;
    
20.                 }
    
21.                 d2type ym=(d2type)y*p.z,pym=(d2type)p.y*z;
    
22.                 return ym<pym;
    
23.         }
    
24. };
    
25. 
    
26. void get_coord(int n, dtype& a, dtype& b)
    
27. {
    
28.         if(n<N){
    
29.                 a=n;b=0;
    
30.         }else if(n<2*N){
    
31.                 a=N;b=n-N;
    
32.         }else if(n<3*N){
    
33.                 a=(3*N-n);b=N;
    
34.         }else{
    
35.                 a=0;b=4*N-n;
    
36.         }
    
37. }
    
38. 
    
39. void get_point(int n1, int n2, int n3, int n4, Point3& p)
    
40. {
    
41.         dtype a,b,c,d,e,f,g,h;
    
42.         get_coord(n1,a,b);get_coord(n2,c,d);get_coord(n3,e,f);get_coord(n4,g,h);
    
43.         p.x=((e - g)*d + (-h*e + g*f))*a + ((-e + g)*c*b + (h*e - g*f)*c);
    
44.         p.y=(f - h)*d*a + (((-f + h)*c + (-h*e + g*f))*b + (h*e - g*f)*d);
    
45.         p.z=(f - h)*a + ((-e + g)*b + ((-f + h)*c + (e - g)*d));
    
46.         if(p.z<0){
    
47.                 p.z=-p.z;
    
48.                 p.y=-p.y;
    
49.                 p.x=-p.x;
    
50.         }else if(p.z==0&&p.y<0){
    
51.                 p.y=-p.y;
    
52.                 p.x=-p.x;
    
53.         }
    
54. }
    
55. 
    
56. 
    
57. void output(const Point3& p)
    
58. {
    
59.         std::cout<<p.x<<","<<p.y<<","<<p.z<<std::endl;
    
60. }
    
61. 
    
62. void get_start_end(int i, int& js, int& je)
    
63. {
    
64.         if(i<N){
    
65.                 js = N+1;
    
66.         }else if(i<2*N){
    
67.                 js = 2*N+1;
    
68.         }else if(i<3*N){
    
69.                 js = 3*N+1;
    
70.         }else{
    
71.                 js=4*N;
    
72.         }
    
73.         if(i==0){
    
74.                 je=3*N-1;
    
75.         }else{
    
76.                 je=4*N-1;
    
77.         }
    
78. }
    
79. 
    
80. int get_edge_by_count(int c)
    
81. {
    
82.         long r=(long)round(sqrt(1+c*8.0));
    
83.         if(r*r!=1+c*8L){
    
84.                 std::cerr<<"count "<<c<<" looks invalid\n";
    
85.                 exit(-1);
    
86.         }
    
87. 
    
88.         return (r+1)/2;
    
89. }
    
90. 
    
91. int main()
    
92. {
    
93.     std::map<Point3, int> points;
    
94.     std::map<Point3, int> sympoints;
    
95.     std::map<int, int> cmap;
    
96.     int i;
    
97.     for(i=0;i<=2*N;i++){
    
98.             int j;
    
99.             int jstart,jend;
    
100.             get_start_end(i,jstart,jend);
     
101.             for(j=jstart;j<=jend;j++){//line from point i to point j
     
102.                     if(i>N/2&&i<2*N+N/2&&j>N/2&&j<2*N+N/2)continue;
     
103.                     if(i>N+N/2&&i<3*N+N/2&&j>N+N/2&&j<3*N+N/2)continue;
     
104.                     int s,t;
     
105.                     for(s=i+1;s<j;s++){
     
106.                             int tstart,tend;
     
107.                             get_start_end(s,tstart,tend);
     
108.                             if(tstart<j+1)tstart=j+1;
     
109.                             for(t=tstart;t<=tend;t++){//next line from s to t
     
110.                                     Point3 p;
     
111.                                     get_point(i,j,s,t,p);
     
112.                                     if(p.x>=p.y&&2*p.x<=N*p.z){
     
113.                                             if(p.x==p.y||2*p.x==N*p.z){
     
114.                                                     if(2*p.x!=N*p.z||p.x!=p.y){
     
115.                                                             sympoints[p]++;
     
116.                                                     }
     
117.                                             }else{
     
118.                                                 points[p]++;
     
119.                                             }
     
120.                                     }
     
121.                             }
     
122.                     }
     
123.             }
     
124.     }
     
125.     long degsums=0;
     
126.     degsums=4*(2*N-1)+(4*N-4)*(3*N-1)+8*N;
     
127.     for(auto p:points){
     
128.             int ec=get_edge_by_count(p.second);
     
129.             degsums+=16*ec;
     
130.             cmap[ec]+=8;
     
131.     }
     
132.     for(auto p:sympoints){
     
133.             int ec=get_edge_by_count(p.second);
     
134.             degsums+=8*ec;
     
135.             cmap[ec]+=4;
     
136.     }
     
137.     cmap[2*N]++;
     
138.     degsums+=4*N;
     
139.     degsums/=2;//num of edges
     
140.     long numnodes = 8*points.size()+4*sympoints.size()+4*N+1;
     
141.     std::cout<<N<<" "<<numnodes<<" "<<degsums-numnodes+1<<std::endl;
     
142.     std::cout<<"{ ";
     
143.     for(auto p:cmap){
     
144.             std::cout<<p.first<<"->"<<p.second<<" ";
     
145.     }
     
146.     std::cout<<"}\n";
     
147.     return 0;
     
148. }
     

复制代码

其中前136项已经提交到OEIS, 现在计算机还在计算中，后面主要瓶颈在于内存。
136项以后有
项数    点数         区域数   
137 2799111561 2852305564
138 2802295529 2885610248
139 2968204097 3023971364
140 2910421145 3018970376
141 3106485517 3178850140
142 3206824821 3277434288
143 3272404781 3354411404
144 3261033533 3381583448
145 3467680413 3551349400
146 3586980529 3665068784
147 3629800925 3730279736
148 3757489605 3850787144
149 3927242969 3998841568
150 3867752689 4000300016
151 4144009073 4219108464
152 4150282137 4265220392
153 4271295825 4385633048
154 4347603237 4478109376
155 4541859465 4647072672
156 4540575149 4690623000
157 4846820121 4933832076
158 4934850625 5037730120
159 5049794561 5159179864

iseemu2009

mathe 发表于 2025-4-16 21:58
下面这段C++代码，通过修改宏N,就可以计算第N项的结果。

更希望你把怪兽那个程序发出来

mathe

gend12.tgz (58.13 KB, 下载次数: 1)

3 天前 上传

点击文件名下载附件

以n=12为例子，可以做出每个大于等于3的交叉点所经过的直线段
可以看出，对于那些经过直线段多的都非常规律，但是稍微少一些的就不规律了。