The New Sudoku Players' Forum

[dobrichev]

Conjecture: Every Sudoku solution, represented as a number, is divisible by 999999999 without remainder.

[blue]

Amazing

These might be valid too:

1) For NxN latin squares with odd N and "digits" either (1,...,N) or (0,...,N-1), the N*N-digit base N+1 number with digits taken from the grid,
is divisible by the N-digit base (N+1) number where each digit is N. Example: 9x9 grid, base 10 -> divisible by 999999999 (base 10).

2) For NxN latin squares with even N and "digits" (0,...,N-1), the N*N-digit base N number with digits taken from the grid,
is divisible by the N-digit base N number where each digit is (N-1). Example: 10x10 grid, base 10 -> divisible by 9999999999 (base 10).

They were valid for 100000 random latin squares each, for sizes N=1,2,...,26.

[coloin]

Wow ... nice conjecture

prime factorizing 999999999 ... you get 3^4 × 37 × 333667

We can easily prove its divisible by 9 because each row always adds up to 45 ..so it will always be divisible by 9

not sure how to prove the second 9

There are block rules for 37 and 111 which looks like it will be extendable to 999 [9x111]

Code: Select all

The 3-Digit Grouping Rule
For larger numbers, it is often faster to use the base-1000 grouping method because 999 is a multiple of 37  (37x27 = 999)
Split the number into groups of three digits starting from the right.
Add all these 3-digit groups together.
If the sum is still large, repeat the addition.If the final sum is divisible by 37, the original number is divisible by 37.

Not sure about 333667 though !

[dobrichev]

Congratulations to Blue for his wonderful generalization!

The applicability to Latin Squares of any size makes it unlikely that the conjecture is new. However, I can't find anything similar on the web.
If it is indeed new, I think it deserves popularization.

Of the factors for N=9, 3 * 333667 = 001001001 and may act as a mask.

[dobrichev]

Likely the conjecure can be further relaxed.

For 9 digit, a number is divisible by 999999999 if it is
sum(n=1..9 (sum(c=0..8 n*10^(9*r+c))) where r is an arbitrary natural number, which may be different for each of the addends.

Row doesn't matter, each digit must occur exactly once at each column.
So, Latin square and Sudoku are just special compact square cases.

Below are some examples, all divisible by 999999999.

Code: Select all

111111111
222222222
333333333
444444444
555555555
666666666
777777777
888888888
999999999 // canonical

222222222
111111111
333333333
444444444
555555555
666666666
777777777
888888888
999999999 // rows 1 and 2 exchanged

111111111
222222229
333333333
444444444
555555555
666666666
777777777
888888888
999999992 // rightmost 2 and 9 exchanged

111111111
222222222
333333333
444444444
000000000
555555555
666666666
777777777
888888888
999999999 // extra row with 0

111111111
222222222
333333333
000044444
444400000
555555555
666666666
777777777
888888888
999999999 // extra 0 spread in two rows


[Serg]

Hi, people!
It looks like I've found proof for the Latin Square case.
Let's consider an example of 9x9 LS with 1..9 digits. 81-digit "LS number" can be presented as sum: "72-digit number" x 10^9 + "9-digit LS last row".

Because (A + B) mod C = ((A mod C) + (B mod C)) mod C,
"LS number" mod 999999999 = ((("72-digit number" x 10^9) mod 999999999) + ("9-digit LS last row" mod 999999999)) mod 999999999.

("72-digit number" x 10^9) mod 999999999 = ("72-digit number" x (999999999+1)) mod 999999999 = "72-digit number" mod 999999999.

We'll continue 9 times such transformation, coming to "63-digit number", "54-digit number", etc. At finish we'll have:
"LS number" mod 999999999 = (("9-digit LS row1" mod 999999999) + ("9-digit LS row2" mod 999999999) + ... + ("9-digit LS last row" mod 999999999)) mod 999999999

"9-digit LS last row" is less than 999999999, so ("9-digit LS last row" mod 999999999) = "9-digit LS last row". Similarly
"9-digit LS row1" mod 999999999 = "9-digit LS row1", etc.

"LS number" mod 999999999 = ("9-digit LS row1" + "9-digit LS row2" + ... + "9-digit LS last row") mod 999999999

"9-digit LS row1" + "9-digit LS row2" + ... + "9-digit LS last row" = 45 x 111111111 = 5 x 999999999

(5 x 999999999) mod 999999999 = 0.

Serg

[blue]

Row doesn't matter, each digit must occur exactly once at each column.

Nice observation.

It makes the conjectures easy to prove.
I can add one more "latin squares" case:

3) For NxN latin squares with even N and "digits" (1,...,N), the N*N-digit base N+2 number with digits taken from the grid,
is divisible by the N-digit base N+2 number where each digit is (N+1). Example: 8x8 grid, base 10 -> divisible by 99999999 (base 10).

If the digits are (0,1,...,N-1), and the "base", B, satisfies "N*(N-1)/2 is a multiple of (B-1)", then it's true.
-- odd N => B = N+1 works, even N => B = N works.
If the digits are (1,...,N), and the "base", B, satisfies "N*(N+1)/2 is a multiple of (B-1)", then it's true.
-- odd N => B = N+1 works, even N => B = N+2 works.

The applicability to Latin Squares of any size makes it unlikely that the conjecture is new. However, I can't find anything similar on the web.
If it is indeed new, I think it deserves popularization.

Indeed.

@Serg - Sorry I stepped on your post. It came up while I was preparing this one. Looking forward to reviewing your proof ...

[Serg]

Hi!
Some addition: if we treat "LS number" as decimal number, then "LS 8x8 number" (number range: 1..8), "LS 9x9 number" (0..8), "LS 9x9 (1..9) and "LS 10x10 number" (0..9) are always divisible by 99...9 (N "9" digits).

Serg

[Edited. I corrected a typo.]

[dobrichev]

Hi Serg,
After rereading your proof several times, I consider the proof to be correct.