Kakuro: The K-factor

For fans of Kakuro

Kakuro: The K-factor

Postby Mathimagics » Mon Apr 18, 2016 11:01 am

Here we look at various properties of Kwords, which are the numbers that can appear in a standard Kakuro puzzle. A Kword is any number > 9 with no zeroes in it, and with no digit repeated.

There are 986400 different Kwords.

K(W) = Kword counts for word length W:

  • word length 2: 72
  • word length 3: 504
  • word length 4: 3024
  • word length 5: 15120
  • word length 6: 60480
  • word length 7: 181440
  • word length 8: 362880
  • word length 9: 362880

There is a simple formula for K(W). We can choose the digits in C(9, W) ways, and then permute them to obtain C(9, W) * W! different words.

This can be generalised to D-digit words, ie. words whose digits can have D different values. We have K(D, W) = C(D, W) * W!, so in a Hex-Kakuro puzzle (ie. with D=16), the table of Kword counts would be:

  • word length 2: 240
  • word length 3: 3360
  • word length 4: 43680
  • word length 5: 524160
  • word length 6: 5765760
  • word length 7: 57657600
  • word length 8: 518918400
  • word length 10: 4151347200
  • word length 11: 29059430400
  • word length 12: 174356582400
  • word length 13: 871782912000
  • word length 14: 3487131648000
  • word length 15: 10461394944000
  • word length 16: 20922789888000

The total number of words for D = 16 would thus be a rather daunting 56,874,039,553,200. :?

Next we will look at interesting number-theoretic properties of standard (D = 9) Kwords.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kwords - Primality

Postby Mathimagics » Mon Apr 18, 2016 11:07 am

Numbers of Kwords which are primes, (P), and whose reversal is also a prime (RP) .

  • word length 2: P = 20, RP = 4
  • word length 3: P = 83, RP = 9
  • word length 4: P = 395, RP = 33
  • word length 5: P = 1610, RP = 135
  • word length 6: P = 5045, RP = 318
  • word length 7: P = 12850, RP = 658
  • word length 8: P = 23082, RP = 1080

RP (reversible prime) lists for W = 2,3,4. The reversals themselves are not listed:

. 13, 17, 37, 79

. 149, 157, 167, 179, 347, 359, 389, 739, 769

. 1237, 1249, 1259, 1279, 1283, 1429, 1439, 1453, 1487, 1523, 1583, 1597, 1657, 1723, 1753, 1789, 1847, 1867, 1879, 3169, 3257, 3467, 3469, 3527, 3697, 3719, 3917, 7219, 7349, 7459, 7529, 7589, 7649


Speaking of reversals, here's a curious fact: there are only 2 cases where a Kword is a multiple of its reversal.

. 8712 = 2178 x 4

. 87912 = 21978 x 4
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kwords - Squares

Postby Mathimagics » Mon Apr 18, 2016 12:04 pm

Kwords that are square are relatively rare:

  • word length 2: 6
  • word length 3: 13
  • word length 4: 21
  • word length 5: 42
  • word length 6: 32
  • word length 7: 36
  • word length 8: 21
  • word length 9: 30

A complete list is given, where (*) indicates thosethat are Ksquares, ie. Kwords that are squares of Kwords:

Hidden Text: Show
  • W = 2: 16, 25, 36, 49, 64, 81
  • W = 3: *169, *196, *256, *289, *324, *361, *529, *576, *625, *729, *784, *841, *961
  • W = 4: *1296, *1369, *1764, *1849, 1936, *2916, *3249, *3481, *3721, 4356, *4761, *5184, *5329, *5476, *6241, *6724, *7396, *7569, *7921, *8649, *9216
  • W = 5: 12769, 13456, 13689, 13924, *15376, *15876, *16384, 17689, *17956, *18496, *18769, *23716, *28561, *29584, *31684, 32761, *34596, *35721, 36481, *37249, *38416, 43681, *45369, *45796, *47961, 51984, 53824, 54289, *71289, *71824, *72361, 73984, *74529, *78961, 79524, *81796, *82369, *83521, 85264, 92416, 95481, 96721
  • W = 6: *132496 *134689, *139876, 195364, *214369, *237169, *279841, *293764, *321489, *327184, *329476, *346921, *349281, *351649, 379456, *381924, *385641, 391876, *395641, 436921, 458329, *524176, 537289, 543169, *582169, 651249, *687241, *729316, *751689, *758641, 781456, *872356
  • W = 7: 1238769, 1247689, 1354896, 1382976, *1763584, 2374681, *2537649, 3297856, 3481956, *3594816, *3857296, 4519876, 5184729, 5391684, 5673924, 5827396, *5948721, 6385729, 6395841, 6538249, *6853924, 7139584, 7214596, 7349521, 7436529, *7458361, 8213956, 8317456, 8473921, 8567329, 9247681, 9253764, 9357481, 9572836, 9678321, *9872164
  • W = 8: *13498276, *13527684, 13942756, 21473956, 21743569, 23174596, *24137569, 34857216, 36517849, 38142976, 41783296, 41938576, 45387169, 45738169, 46389721, 52374169, 54213769, 65318724, 73256481, *74356129, 81432576
  • W = 9: 139854276, 152843769, *157326849, 215384976, 245893761, *254817369, 326597184, 361874529, 375468129, 382945761, 385297641, 412739856, 523814769, 529874361, *537219684, 549386721, 587432169, 589324176, 597362481, 615387249, 627953481, 653927184, *672935481, 697435281, 714653289, 735982641, 743816529, 842973156, 847159236, 923187456
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kwords - Cubes

Postby Mathimagics » Mon Apr 18, 2016 12:30 pm

Kwords that are cubes are also rare:

  • word length 2: 2
  • word length 3: 4
  • word length 4: 6
  • word length 5: 7
  • word length 6: 5
  • word length 7: 1
  • word length 8: 2
  • word length 9: 0

A complete list: (*) indicates Kcubes, ie. Kwords that are cubes of Kwords:

Hidden Text: Show
  • W = 2: 27, 64
  • W = 3:125, 216, 512, 729
  • W = 4: *1728, *2197, *4913, *5832, *6859, *9261
  • W = 5: *13824, *19683, *24389, *32768, *42875, *54872, *68921
  • W = 6: 287496, *421875, *438976, 681472, *912673
  • W = 7: 8365427
  • W = 8: *24137569, *32461759
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kwords - Higher powers

Postby Mathimagics » Mon Apr 18, 2016 1:14 pm

.
17 is unique, as 4 of its higher powers are Kwords:

  • 17^2 = 289, 17^3 = 4913, 17^4 = 83521, 17^6 = 24137569

Other cases of higher powers of Kwords:

  • 13^4 = 28561, 23^4 = 279841


Other Kwords that are higher powers, although not of another Kword:

  • 16 = 2^4, 32 = 2^5, 64 = 2^6, 128 = 2^7, 256 = 2^8, 512 = 2^9, 8192 = 2^13, 16384 = 2^14, 32768 = 2^15

  • 81 = 3^4, 243 = 3^5, 729 = 3^6, 2187 = 3^7, 19683 = 3^9

  • 625 = 5^4, 3125 = 5^5, 78125 = 5^7
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kwords - Prime factors all Kwords

Postby Mathimagics » Mon Apr 18, 2016 1:48 pm

Kwords (other than those that are primes) whose prime factors are all Kwords:

  • word length 3: 25
  • word length 4: 183
  • word length 5: 839
  • word length 6: 2413
  • word length 7: 5022
  • word length 8: 6681
  • word length 9: 0

There are no entries for word length 9 because all 9-digit Kwords are divisible by 3, which is not a Kword.

The list for word length 3:

  • 169 = 13 x 13, 247 = 13 x 19, 289 = 17 x 17, 361 = 19 x 19, 391 = 17 x 23
  • 437 = 19 x 23, 481 = 13 x 37, 493 = 17 x 29, 527 = 17 x 31, 529 = 23 x 23
  • 589 = 19 x 31, 629 = 17 x 37, 689 = 13 x 53, 697 = 17 x 41, 713 = 23 x 31
  • 731 = 17 x 43, 793 = 13 x 61, 817 = 19 x 43, 841 = 29 x 29, 851 = 23 x 37
  • 871 = 13 x 67, 893 = 19 x 47, 923 = 13 x 71, 943 = 23 x 41, 961 = 31 x 31

Examples with maximum number of distinct Kword-prime factors:

  • 4816253 = 13 x 17 x 19 x 31 x 37
  • 15286973 = 13 x 23 x 29 x 41 x 43
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kwords - Compositions

Postby Mathimagics » Mon Apr 18, 2016 6:50 pm

A partition is a representation of a number N as a set of values that either add up to N (additive partition) or multiply out to N (multiplicative partition, or MP).

An MP is simply a factorisation of N into 2 or more parts. Note that we exclude trivial factors (1, N). We write NMP for the number of different MP's.

For example NMP(24) = 6. The factorisations are:

  • {2, 2, 2, 3}, {2, 2, 6}, {2, 3, 4}, {2, 12}, {3, 8}, {4, 6}

A composition of a Kword K is a multiplicative partition of K in which each factor is itself a Kword. We write NKC(K) for the number of compositions.

For example, 6174 has 5 different compositions:

  • {14, 21, 21}
  • {21, 294}
  • {42, 147}
  • {49, 126}
  • {63, 98}

Numbers with many prime factors (smooth numbers) generally have the highest NMP. These can be surpisingly high. The record holder for a Kword is 536481792 = 2^12 x 3^5 x 7^2 x 11, which has over a million distinct factorisations, NMP = 1,082,006.

Record holders for NKC, with corresponding K value:

  • word length 3: NKC = 5, K = 672
  • word length 4: NKC = 22, K = 8736
  • word length 5: NKC = 87, K = 78624
  • word length 6: NKC = 249, K = 746928
  • word length 7: NKC = 954, K = 6971328
  • word length 8: NKC = 2311, K = 95641728
  • word length 9: NKC = 8034, K = 753846912

For K = 753846912, 16 of the 8034 compositions have 7 factors. These are shown here:

Hidden Text: Show
  • {12, 12, 12, 13, 14, 47, 51}
  • {12, 12, 12, 13, 17, 21, 94}
  • {12, 12, 12, 13, 17, 42, 47}
  • {12, 12, 12, 13, 21, 34, 47}
  • {12, 12, 12, 14, 17, 39, 47}
  • {12, 12, 12, 17, 21, 26, 47}
  • {12, 12, 13, 14, 17, 18, 94}
  • {12, 12, 13, 14, 17, 36, 47}
  • {12, 12, 13, 14, 18, 34, 47}
  • {12, 12, 13, 17, 18, 28, 47}
  • {12, 12, 13, 17, 21, 24, 47}
  • {12, 12, 14, 17, 18, 26, 47}
  • {12, 13, 14, 16, 17, 27, 47}
  • {12, 13, 14, 17, 18, 24, 47}
  • {12, 13, 16, 17, 18, 21, 47}
  • {13, 14, 16, 17, 18, 18, 47}
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Kwords - Pure Compositions

Postby Mathimagics » Mon Apr 18, 2016 7:46 pm

.
Perhaps the most elegant Kwords of all are those with "pure compositions". These are compositions in which no digit is repeated in the set of factors, ie. their concatenation is a Kword.

For example there are two PC's for 6174, namely {49, 126} and {63, 98}.

The record number of PC's is 11, which is shared by K = 275184, 689472 and 3619728.

The perfect compositions of 275184:
Hidden Text: Show
  • {13, 28, 756}
  • {14, 52, 378}
  • {18, 24, 637}
  • {18, 56, 273}
  • {36, 52, 147}
  • {36, 84, 91}
  • {39, 42, 168}
  • {48, 63, 91}
  • {52, 63, 84}
  • {84, 3276}
  • {351, 784}

The perfect compositions of 689472:
Hidden Text: Show
  • {16, 54, 798}
  • {19, 48, 756}
  • {19, 54, 672}
  • {24, 36, 798}
  • {24, 38, 756}
  • {57, 63, 192}
  • {57, 64, 189}
  • {54, 12768}
  • {96, 7182}
  • {432, 1596}
  • {756, 912}

The perfect compositions of 3619728:
Hidden Text: Show
  • {12, 57, 63, 84}
  • {21, 36, 57, 84}
  • {21, 48, 57, 63}
  • {21, 378, 456}
  • {27, 84, 1596}
  • {54, 72, 931}
  • {56, 189, 342}
  • {57, 196, 324}
  • {72, 98, 513}
  • {456, 7938}
  • {798, 4536}


For perfect compositions using all 9 digits, the smallest is 8532496, with composition {14, 29, 37, 568}.

There are 4 x 9-digit Kwords which each have 3 PC's using all 9 digits:

  • 125793486: {49, 53, 78, 621}, {42, 819, 3657}, {91, 567, 2438}
  • 194325768: {56, 819, 4237}, {78, 2491356}, {798, 243516}
  • 217845936: {59, 63, 72, 814}, {42, 531, 9768}, {5841, 37296}
  • 419527836: {51, 972, 8463}, {62, 91, 74358}, {63, 918, 7254}
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015


Return to Kakuro