整数边长凸等角六边形

iseemu2009

令H(n) 表示周长不超过 n 不同整数边长等内角凸六边形的数量，不同意味着不全等。
比如 H(6)=1, H(12)=10, H(100)=31248, 求H(55106)。

mathe

如图，记六边依次为a,b,c,d,e,f, 设`ω`为三次单位根，

则\[
a-bω^2+cω-d+eω^2-fω=0\\
(a-d)+(c-f)ω+(e-b)ω^2=0\\
→  a-d=c-f=e-b\]
于是可设`a=d + g, c=f + g, e=b + g`, 周长为 `n` 的六边形的数量即丢番图方程\[
2(b+d+f)+3g=n,(0<b≤d≤f, 0≤g)\]的解数。

mathe

为了计数方便，我们可以记$\delta(n)$在n为3的倍数为1，在n不是三的倍数为0.
我们先求b+d+f=m的非负整数解的数目，
其中b=d=f的解有$\delta(m)$个。
而b,d,f中正好两个数相等的解数目为$[(m+2)/2]-\delta(m)$。(要求三个数从小到大)
而b+d+f=m不限制三个数的顺序解的数目为${(m+2)(m+1)}/2$,
所以要求三数不同而且有序数目为${{(m+2)(m+1)}/2-3[(m+2)/2]+2delta(m)}/6$.
而三个数有序而且可以相等的数目为$U(m)={{(m+2)(m+1)}/2-3[(m+2)/2]+2delta(m)}/6+[(m+2)/2]$
然后假设边长等于n的不全等六边形数目为K(n),
这需要求2(b+d+f)+3h=n奇偶解的数目，其中h非负整数，b,d,f为大于0的整数。
而h的奇偶性显然必须和n相同。另外b,d,f都减1可以转化为非负整数。所以只要枚举h然后用U((n-6-3h)/2)求和即可。最后应该根据n模12的不同余数均可以给出公式解

mathe

于是U(n)必然可以写成$an^2+bn+c+d(-1)^n+ew^n+fw^(-n)$,
其中$w$为三次单位根。
周长为n的等角六边形K(n)为$U((n-6-3h)/2)$对h求和，我们需要分奇偶和模三次数求和，所以最终表达式应该类似上面，只是n的多项式次数达到了三次。而题目中所求为K(n)前n项之和，所以H(n)最终结果表达式还是类似，只是n变成四次多项式，最终应该是一个八阶递推式

iseemu2009

根据题目描述，等角对于所有情况都是120度吗？所有图形对边都平行吗？你们的分析中有没有相关的证明，有没有例外的情况？

mathe

现在利用上面公式可以先将H的前面若干项计算出来
0, 0, 0, 0, 0, 1, 1, 2, 3, 5, 6, 10, 12, 17, 21, 28, 33, 44, 51, 64, 75, 92, 105, 128, 145, 172, 195, 228, 255, 297, 330, 378, 420, 477, 525, 594, 651, 729, 798, 888, 966, 1072, 1162, 1280, 1386, 1520, 1638, 1792, 1926, 2096, 2250, 2440, 2610, 2825, 3015, 3250, 3465, 3725, 3960, 4250, 4510, 4825, 5115, 5460, 5775, 6156, 6501, 6912, 7293, 7740, 8151, 8640, 9087, 9612, 10101, 10668, 11193, 11809, 12376, 13034, 13650, 14357, 15015, 15778, 16485, 17297, 18060, 18928, 19740, 20672, 21540, 22528, 23460, 24512, 25500, 26624, 27676, 28864, 29988, 31248, 32436, 33777, 35037, 36450, 37791, 39285, 40698, 42282, 43776, 45441, 47025, 48780, 50445, 52300, 54055

mathe

验算得出递推式竟然高达16阶，为
v[u]=v[u-1]+v[u-2]-2*v[u-5]+v[u-6]-v[u-7]+v[u-9]-v[u-10]+2*v[u-11]-v[u-14]-v[u-15]+v[u-16]

最后可以得出
H[55106]=2668608479740672

然后可以得到公式
\[H(n)=\frac{n^4}{3456}+\frac{n^3}{432}-\frac{n^2}{384}-\frac{25n}{864}-\frac{23}{6912}+(\frac{n^2}{384}+\frac{n}{96}-\frac{19}{2304})(-1)^n+ \frac{1+\sqrt{3}i}{72}w^n+\frac{1-\sqrt{3}i}{72}w^{-n}
-\frac{i^n+(-i)^n}{32}+(\frac{3+\sqrt{3}i}{324}n+ \frac{15+\sqrt{3}i}{648})(-w)^{-n}+(\frac{3-\sqrt{3}i}{324}n+ \frac{15-\sqrt{3}i}{648})(-w)^n\]

iseemu2009

mathe 发表于 2025-3-14 08:42
验算得出递推式竟然高达16阶，为
v=v[u-1]+v[u-2]-2*v[u-5]+v[u-6]-v[u-7]+v[u-9]-v[u-10]+2*v[u-11]-v[u-1 ...

思路很好，验算答案也是正确的，这个递推式是怎么得到的？

mathe

最后表达式可以简化为
$\text{round}(n^4/3456+n^3/432-n^2/384-{25n}/864+(n^2/384+n/96)(-1)^n+(3+sqrt(3)i)/324n(-w)^(-n)+(3-sqrt(3)i)/324n(-w)^n)$

王守恩

这题目挺不错的！！！谢谢 iseemu2009！！！

{0, 0, 0, 0, 0, 1, 1, 2, 3, 5, 6, 10, 12, 17, 21, 28, 33, 44, 51, 64, 75, 92, 105, 128, 145, 172, 195, 228, 255, 297, 330, 378, 420, 477, 525, 594, 651, 729, 798, 888, 966, 1072, 1162, 1280, 1386, 1520, ...——H(n)

LinearRecurrence[{1, 1, 0, 0, -2, 1, -1, 0, 1, -1, 2, 0, 0, -1, -1, 1}, {0, 0, 0, 0, 0, 1, 1, 2, 3, 5, 6, 10, 12, 17, 21, 28}, 50]
......
LinearRecurrence[{1, 1, 0, 0, -2, 1, -1, 0, 1, -1, 2, 0, 0, -1, -1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 5}, 50]
......
LinearRecurrence[{1, 1, 0, 0, -2, 1, -1, 0, 1, -1, 2, 0, 0, -1, -1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, 50]
......
LinearRecurrence[{1, 1, 0, 0, -2, 1, -1, 0, 1, -1, 2, 0, 0, -1, -1, 1}, {5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 50]
......
这样都是可以的。

{0, 0, 0, 0, 0, 1, 1, 2, 3, 5, 6, 10, 12, 17, 21, 28, 33, 44, 51, 64, 75, 92, 105, 128, 145, 172, 195, 228, 255, 297, 330, 378, 420, 477, 525, 594, 651, 729, 798, 888, 966, 1072, 1162, 1280, 1386, 1520, ...——H(n)
后项-前项=这样一串数。
{0, 0, 0, 0, 1, 0, 1, 1, 2, 1, 4, 02, 05, 04, 07, 05, 11, 07, 13, 11, 17, 13, 023, 017, 027, 023, 033, 027, 042, 033, 048, 042, 057, 048, 069, 057, 078, 069, 090, 078, 106, 0090, 0118, 0106, 0134, ...... ——A(n)
LinearRecurrence[{0, 1, 1, 1, -1, 0, -1, -1, 0, -1, 1, 1, 1, 0, -1}, {0, 0, 0, 0, 1, 0, 1, 1, 2, 1, 4, 2, 5, 4, 7}, 50]
再:隔一提一。
0, 0, 1, 1, 2, 4, 5, 7, 11, 13, 17, 23, 27, 33, 42, 48, 57, 69, 78, 90, 106, 118, 134, 154, 170, 190, 215, 235, 260, 290, 315, 345, 381, 411, 447, 489, 525, 567, 616, 658, 707, 763, 812, ——A307872—— Jan 14 2024
LinearRecurrence[{1, 1, 1, -2, -2, 1, 1, 1, -1}, {0, 0, 0, 1, 1, 2, 4, 5, 7}, 115]
H(n)也可以这样。

1. Table[Sum[Round[((2 n^2 + 9 n + 96 (Floor[n/3] - Floor[(n - 1)/3]) + 9 (n + 3) Cos[n Pi] - 51) n)/1728], {n, 0, k}], {k, 50}]

复制代码

A(n)就是这样了。

1. Table[Round[((2 n^2 + 9 n + 96 (Floor[n/3] - Floor[(n - 1)/3]) + 9 (n + 3) Cos[n Pi] - 51) n)/1728], {n, 50}]

复制代码