The New Sudoku Players' Forum

[Red Ed]

Thought someone might find the following interesting. ... The 3xC slope ends up around 0.9031

Perhaps you knew this anyway, but N(3,C) is the Cth Franel number. Asymptotically, this is O(8^C), confirming that the slope on your graph should be log10(8) ~= 0.9031.

[PatmaxDaddy]

I've reentered the corrected values for 5x7 and 5x8, which were lost when the database was restored from backup a few days ago. The post describing the changes is lost, but essentially the errors were caused by overflows that I have since corrected. The challange is knowing when to switch from using native data types that are very fast but can overflow silently, to my arbitrary-precision fixed point class, which cannot overflow but which is much slower. I'm being more careful now.

[PatmaxDaddy]

Perhaps you knew this anyway, ...

No, I've never heard of Franel numbers, thanks for pointing that out. I learned enough math to get an MS in electrical engineering, which is a lot but not nearly as much as the regulars who post here know.

I was hoping that these graphs might offer some clue about how the RxC values behave in general, a clue that might allow us to estimate higher values than those we can compute, and maybe use them to estimate grid counts above 6x6. Anyone have any ideas?

[kjellfp]

Here is a plot of log10(N) as a function of C for R=3 (blue), R=4 (yellow), and R=5 (magenta).

Thanks for a very interresting diagram. I got the impression that N(R,C+1)/N(R,C) had a limit for C -> infinity when I first produced the results for 4xC, but your diagram really demonstrates this visually.

As a mathematician I'd like to determine whether these limits can be calculated explicitely.

[kjellfp]

The 3xC slope ends up around 0.9031

Red Ed has already pointed out that the limit is log10(8) = 0.903089987.

I was giving it a thought when I went to bed yesterday.

N(3,C) = sum_k bin(C,k)^3. The most dominating terms are for k near C/2.

We have bin(C,k)/bin(C-1,k-1) = C/k, for k near C/2 this is close to 2. For three-powers, this is close to 8.

So when we sum some of the terms for N(3,C) where k is close to C/2, and divide by the corresponding terms for N(3,C-1), we get something close to 8. The terms further away from C/2 are much smaller.

This is how I can imagine that N(3,C)/N(3,C-1) approaches 8. I don't think it's too difficult to give a strict mathematical proof which more formally handles the side effects of the lower terms.

We might even read the corresponding ratios for higher values of R from the formulaes or the algorithm.

[kjellfp]

The 3xC slope ends up around 0.9031, 4xC around 3.1, and 5xC is around 6.5 or so for the low values of C that I've been able to run.

A corresponding argument to the one used for 3xC has been applied to general R by looking at the RxC algorithm. It looks like N(R,C)/N(R,C-1) will approach (R-1)!^R when C goes to infinity. Some log10-values of this:

R=3: 0.903090
R=4: 3.112605
R=5: 6.901056
R=6: 12.475087

etc.

I'll come back to an explaination on my approximations.

[Red Ed]

This is how I can imagine that N(3,C)/N(3,C-1) approaches 8. I don't think it's too difficult to give a strict mathematical proof which more formally handles the side effects of the lower terms.

I went with the recurrence relation n^2 F(n) = (7n^2 - 7n + 2) F(n-1) + 8(n - 1)^2 F(n-2).
As n->infinity, this is F(n) = 7F(n-1) + 8F(n-2), so F(n) = multiple of (-1)^n or 8^n.

[kjellfp]

This implies that there is a reccursion formula for N(3,C) with respect to C.

This of course raises the question: Is there a reccursion formula for N(R,C) for any R? How deep is it? Could this be used to determine PatmaxDaddy's 5xC-sequence further in just a fraction of a second?

[kjellfp]

This of course raises the question: Is there a reccursion formula for N(R,C) for any R? How deep is it? Could this be used to determine PatmaxDaddy's 5xC-sequence further in just a fraction of a second?

1. Yes, most certainly
2. VERY deep
3. Definitely not, because (a) I don't think we will find the formula, and (b) still if we did, we would have to precalculate much more 5xC-values than we have now before the reccursion formula could be used.

All this because I'm sure I have found the 4xC reccursion formula. I have not proved it explicitely (and I don't think I will ever dear), but there are good reasons to believe it's correct.

Let R(C) be the number of RxC-bands divided by (4C)! * C!^12. From the experience with 3xC (the Franell numbers) it's reasonable to guess that R(C) fits into som reccursion forumla

Code: Select all

F_0(C) * R(C) + F_1(C) * R(C-1) + ... + F_N(C) * R(C-N) = 0

where the F_i are polynomials in C.

With some precalculated values of R(C), it's possible to experiment with systems of linear equations to get the polynomial coefficients.

This was best to do modulo a prime first, to get an idea of the reccursion depth and polynomial degrees. Afterwards, I did the calculation with integers and some more R(C) values than those just needed to get the coefficients. The linear system had one non-trivial solution for the guessed degree and depth. Some of the polynomials also had linear factors which fitted into the pattern I could sense in the Franell numbers formula.

For 3xC, depth was 2 and polynomial degree was 2. The coefficients were not bigger than 16.

For 4xC, depth seems to bee 13, polynomial degree is 8, and the biggest coefficient is 2906501472489100167249389420544.

No need to go for the 5xC formula...

The 4xC formula found is given in the next post.

[kjellfp]

The reccursion formula:

If the number of 4xC bands is (4C)! * C!^12 * R(C), then

Code: Select all

71 * F_0(C) * R(C)
+ 8 * F_1(C) * R(C-1)
+ 64 * F_2(C) * R(C-2)
+ 512 * F_3(C) * R(C-3)
+ 4096 * F_4(C) * R(C-4)
+ 32768 * F_5(C) * R(C-5)
+ 262144 * F_6(C) * R(C-6)
+ 4194304 * F_7(C) * R(C-7)
+ 201326592 * F_8(C) * R(C-8)
+ 6442450944 * F_9(C) * R(C-9)
+ 618475290624 * F_10(C) * R(C-10)
+ 178120883699712 * F_11(C) * R(C-11)
+ 1846757322198614016 * F_12(C) * R(C-12)
+ 9573589958277615058944 * F_13(C) * R(C-13)
= 0

where

Code: Select all

F_0(C)  = - C^6 * (C-1)^2
F_1(C)  = (C-1)^2 * [ 171326 - 810515*C + 1560076*C^2 - 1564443*C^3 + 870263*C^4 - 263804*C^5 + 37311*C^6 ]
F_2(C)  = - 830839294 + 3290371761*C - 5802615765*C^2 + 5955176757*C^3 - 3888997199*C^4 + 1652951755*C^5
          - 445790012*C^6 + 69619894*C^7 - 4813367*C^8
F_3(C)  = 312760427352 - 912788970642*C + 1165253562453*C^2 - 850797588265*C^3 + 389100442107*C^4
          - 114310113540*C^5 + 21104767851*C^6 - 2243702981*C^7 + 105425743*C^8
F_4(C)  = 3720103021142 - 3696846458479*C - 785535474276*C^2 + 2860434508346*C^3 - 1842357443022*C^4
          + 602603994380*C^5 - 111628655770*C^6 + 11210591680*C^7 - 477587165*C^8
F_5(C)  = - 797132481675646 + 1299489231533963*C - 916808862420949*C^2 + 364682084171454*C^3
          - 89088752639394*C^4 + 13595829346800*C^5 - 1251273614246*C^6 + 62117635822*C^7 - 1212479636*C^8
F_6(C)  = 3696733170991086 - 7177797506790705*C + 5553140250884337*C^2 - 2323537859876068*C^3
          + 585627694081732*C^4 - 91933956451664*C^5 + 8826580250024*C^6 - 475273401252*C^7 + 11002070436*C^8
F_7(C)  = 79322922412116840 - 83425281275823387*C + 37598964042238470*C^2 - 9402299518397928*C^3
          + 1405635810567280*C^4 - 124924683004160*C^5 + 6004008163344*C^6 - 108710373088*C^7 - 844212016*C^8
F_8(C)  = - 161437697999164515 + 165705982988634480*C - 74306699350927977*C^2 + 19004527819592400*C^3
          - 3030377651015080*C^4 + 308277136686240*C^5 - 19521269783672*C^6 + 702736586472*C^7 - 10994652516*C^8
F_9(C)  = 183648673281809322 - 177108542506870569*C + 74792146023444209*C^2 - 18063629156976634*C^3
          + 2728888216770598*C^4 - 264044128636920*C^5 + 15979121117030*C^6 - 552929120870*C^7 + 8375525860*C^8
F_10(C) = - 31970888811536868 + 28990697313774654*C - 11506943511519192*C^2 + 2611310834912427*C^3
          - 370582947612417*C^4 + 33678338511700*C^5 - 1914087918974*C^6 + 62202279563*C^7 - 884918269*C^8
F_11(C) = 739046950653744 - 638403821233752*C + 240673279532528*C^2 - 51736892746984*C^3 + 6938268781591*C^4
          - 594536866366*C^5 + 31795428556*C^6 - 970416058*C^7 + 12942869*C^8
F_12(C) = (C-11)^4 * [ 2363016 - 452*C - 130144*C^2 + 16689*C^3 - 603*C^4 ]
F_13(C) = - (C-11)^4 * (C-12)^4