It is 72, I think, for x = 125 Yes, you are right. It seems likely that 72 should suffice for all integers x.
What about the sequence: a(n) = smallest k such that ... ? With a(125) = 72. Could you please submit it? (With keyword "base", of course) Neil
Does someone have a proof for k=72 (in decimal)? Sure seems right, but I don't think we've seen an upper bound on the x that attains the maximum k, which would justify computer-based evidence. --Michael On Thu, Dec 15, 2011 at 4:15 PM, N. J. A. Sloane <njas@research.att.com>wrote:
It is 72, I think, for x = 125 Yes, you are right. It seems likely that 72 should suffice for all integers x.
What about the sequence: a(n) = smallest k such that ... ? With a(125) = 72. Could you please submit it? (With keyword "base", of course) Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
Only considering the last four digits, for all values of i between 0 and 10000 not divisible by 10, shows 125 at 72 as the highest (next best is 3375 at 56). This proves that the limit is k=72 at 125, and there is no solution that does not end in "0125" that is not 125 itself. On Thu, Dec 15, 2011 at 1:43 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Does someone have a proof for k=72 (in decimal)? Sure seems right, but I don't think we've seen an upper bound on the x that attains the maximum k, which would justify computer-based evidence.
--Michael
On Thu, Dec 15, 2011 at 4:15 PM, N. J. A. Sloane <njas@research.att.com>wrote:
It is 72, I think, for x = 125 Yes, you are right. It seems likely that 72 should suffice for all integers x.
What about the sequence: a(n) = smallest k such that ... ? With a(125) = 72. Could you please submit it? (With keyword "base", of course) Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Ah, yes, good point. That can turn into a computer search in all bases. Nice. --Michael On Dec 15, 2011 5:09 PM, "Tom Rokicki" <rokicki@gmail.com> wrote:
Only considering the last four digits, for all values of i between 0 and 10000 not divisible by 10, shows 125 at 72 as the highest (next best is 3375 at 56).
This proves that the limit is k=72 at 125, and there is no solution that does not end in "0125" that is not 125 itself.
On Thu, Dec 15, 2011 at 1:43 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Does someone have a proof for k=72 (in decimal)? Sure seems right, but I don't think we've seen an upper bound on the x that attains the maximum k, which would justify computer-based evidence.
--Michael
On Thu, Dec 15, 2011 at 4:15 PM, N. J. A. Sloane <njas@research.att.com wrote:
It is 72, I think, for x = 125 Yes, you are right. It seems likely that 72 should suffice for all integers x.
What about the sequence: a(n) = smallest k such that ... ? With a(125) = 72. Could you please submit it? (With keyword "base", of course) Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Confirmations appreciated. a(1) = 10 a(2) = 45 a(3) = 10 a(4) = 23 a(5) = 18 a(6) = 15 a(7) = 10 a(8) = 12 a(9) = 10 a(10) = 9 a(11) = 10 a(12) = 13 a(13) = 8 a(14) = 17 a(15) = 12 a(16) = 16 a(17) = 7 a(18) = 5 a(19) = 10 a(20) = 45 a(21) = 9 a(22) = 9 a(23) = 9 a(24) = 19 a(25) = 36 a(26) = 15 a(27) = 7 a(28) = 17 a(29) = 7 a(30) = 9 a(31) = 10 a(32) = 18 a(33) = 10 a(34) = 27 a(35) = 16 a(36) = 11 a(37) = 10 a(38) = 5 a(39) = 10 a(40) = 23 a(41) = 9 a(42) = 9 a(43) = 7 a(44) = 9 a(45) = 8 a(46) = 11 a(47) = 10 a(48) = 12 a(49) = 10 a(50) = 18 a(51) = 9 a(52) = 18 a(53) = 8 a(54) = 11 a(55) = 9 a(56) = 12 a(57) = 10 a(58) = 5 a(59) = 10 a(60) = 15 a(61) = 9 a(62) = 9 a(63) = 8 a(64) = 9 a(65) = 11 a(66) = 11 a(67) = 7 a(68) = 14 a(69) = 5 a(70) = 8 a(71) = 10 a(72) = 11 a(73) = 10 a(74) = 7 a(75) = 12 a(76) = 12 a(77) = 7 a(78) = 5 a(79) = 10 a(80) = 12 a(81) = 9 a(82) = 7 a(83) = 10 a(84) = 11 a(85) = 8 a(86) = 11 a(87) = 7 a(88) = 9 a(89) = 9 a(90) = 5 a(91) = 10 a(92) = 6 a(93) = 10 a(94) = 6 a(95) = 7 a(96) = 6 a(97) = 10 a(98) = 8 a(99) = 10 a(100) = 9 a(101) = 9 a(102) = 9 a(103) = 7 a(104) = 9 a(105) = 9 a(106) = 9 a(107) = 7 a(108) = 9 a(109) = 5 a(110) = 9 a(111) = 10 a(112) = 8 a(113) = 8 a(114) = 7 a(115) = 7 a(116) = 11 a(117) = 7 a(118) = 5 a(119) = 9 a(120) = 13 a(121) = 8 a(122) = 8 a(123) = 9 a(124) = 19 a(125) = 72 a(126) = 15 a(127) = 7 a(128) = 7 a(129) = 7 a(130) = 8 a(131) = 8 a(132) = 6 a(133) = 8 a(134) = 7 a(135) = 7 a(136) = 7 a(137) = 8 a(138) = 5 a(139) = 10 a(140) = 17 a(141) = 7 a(142) = 8 a(143) = 7 a(144) = 9 a(145) = 8 a(146) = 5 a(147) = 8 a(148) = 7 a(149) = 7 a(150) = 12 a(151) = 8 a(152) = 6 a(153) = 6 a(154) = 6 a(155) = 7 a(156) = 6 a(157) = 7 a(158) = 5 a(159) = 10 a(160) = 16 a(161) = 7 a(162) = 9 a(163) = 8 a(164) = 9 a(165) = 15 a(166) = 33 a(167) = 7 a(168) = 19 a(169) = 8 a(170) = 7 a(171) = 7 a(172) = 11 a(173) = 6 a(174) = 5 a(175) = 15 a(176) = 11 a(177) = 7 a(178) = 5 a(179) = 7 a(180) = 5 a(181) = 5 a(182) = 5 a(183) = 6 a(184) = 5 a(185) = 9 a(186) = 5 a(187) = 7 a(188) = 5 a(189) = 9 a(190) = 8 a(191) = 10 a(192) = 5 a(193) = 10 a(194) = 5 a(195) = 11 a(196) = 5 a(197) = 10 a(198) = 5 a(199) = 10 a(200) = 45 On Thu, Dec 15, 2011 at 5:24 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
Ah, yes, good point. That can turn into a computer search in all bases. Nice.
--Michael On Dec 15, 2011 5:09 PM, "Tom Rokicki" <rokicki@gmail.com> wrote:
Only considering the last four digits, for all values of i between 0 and 10000 not divisible by 10, shows 125 at 72 as the highest (next best is 3375 at 56).
This proves that the limit is k=72 at 125, and there is no solution that does not end in "0125" that is not 125 itself.
On Thu, Dec 15, 2011 at 1:43 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Does someone have a proof for k=72 (in decimal)? Sure seems right, but I don't think we've seen an upper bound on the x that attains the maximum k, which would justify computer-based evidence.
--Michael
On Thu, Dec 15, 2011 at 4:15 PM, N. J. A. Sloane < njas@research.att.com wrote:
It is 72, I think, for x = 125 Yes, you are right. It seems likely that 72 should suffice for all integers x.
What about the sequence: a(n) = smallest k such that ... ? With a(125) = 72. Could you please submit it? (With keyword "base", of course) Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Agrees with my computations. I am submitting the sequence now. On 12/15/2011 5:25 PM, Allan Wechsler wrote:
Confirmations appreciated.
a(1) = 10 a(2) = 45 a(3) = 10 a(4) = 23 a(5) = 18 a(6) = 15 a(7) = 10 a(8) = 12 a(9) = 10 a(10) = 9 a(11) = 10 a(12) = 13 a(13) = 8 a(14) = 17 a(15) = 12 a(16) = 16 a(17) = 7 a(18) = 5 a(19) = 10 a(20) = 45 a(21) = 9 a(22) = 9 a(23) = 9 a(24) = 19 a(25) = 36 a(26) = 15 a(27) = 7 a(28) = 17 a(29) = 7 a(30) = 9 a(31) = 10 a(32) = 18 a(33) = 10 a(34) = 27 a(35) = 16 a(36) = 11 a(37) = 10 a(38) = 5 a(39) = 10 a(40) = 23 a(41) = 9 a(42) = 9 a(43) = 7 a(44) = 9 a(45) = 8 a(46) = 11 a(47) = 10 a(48) = 12 a(49) = 10 a(50) = 18 a(51) = 9 a(52) = 18 a(53) = 8 a(54) = 11 a(55) = 9 a(56) = 12 a(57) = 10 a(58) = 5 a(59) = 10 a(60) = 15 a(61) = 9 a(62) = 9 a(63) = 8 a(64) = 9 a(65) = 11 a(66) = 11 a(67) = 7 a(68) = 14 a(69) = 5 a(70) = 8 a(71) = 10 a(72) = 11 a(73) = 10 a(74) = 7 a(75) = 12 a(76) = 12 a(77) = 7 a(78) = 5 a(79) = 10 a(80) = 12 a(81) = 9 a(82) = 7 a(83) = 10 a(84) = 11 a(85) = 8 a(86) = 11 a(87) = 7 a(88) = 9 a(89) = 9 a(90) = 5 a(91) = 10 a(92) = 6 a(93) = 10 a(94) = 6 a(95) = 7 a(96) = 6 a(97) = 10 a(98) = 8 a(99) = 10 a(100) = 9 a(101) = 9 a(102) = 9 a(103) = 7 a(104) = 9 a(105) = 9 a(106) = 9 a(107) = 7 a(108) = 9 a(109) = 5 a(110) = 9 a(111) = 10 a(112) = 8 a(113) = 8 a(114) = 7 a(115) = 7 a(116) = 11 a(117) = 7 a(118) = 5 a(119) = 9 a(120) = 13 a(121) = 8 a(122) = 8 a(123) = 9 a(124) = 19 a(125) = 72 a(126) = 15 a(127) = 7 a(128) = 7 a(129) = 7 a(130) = 8 a(131) = 8 a(132) = 6 a(133) = 8 a(134) = 7 a(135) = 7 a(136) = 7 a(137) = 8 a(138) = 5 a(139) = 10 a(140) = 17 a(141) = 7 a(142) = 8 a(143) = 7 a(144) = 9 a(145) = 8 a(146) = 5 a(147) = 8 a(148) = 7 a(149) = 7 a(150) = 12 a(151) = 8 a(152) = 6 a(153) = 6 a(154) = 6 a(155) = 7 a(156) = 6 a(157) = 7 a(158) = 5 a(159) = 10 a(160) = 16 a(161) = 7 a(162) = 9 a(163) = 8 a(164) = 9 a(165) = 15 a(166) = 33 a(167) = 7 a(168) = 19 a(169) = 8 a(170) = 7 a(171) = 7 a(172) = 11 a(173) = 6 a(174) = 5 a(175) = 15 a(176) = 11 a(177) = 7 a(178) = 5 a(179) = 7 a(180) = 5 a(181) = 5 a(182) = 5 a(183) = 6 a(184) = 5 a(185) = 9 a(186) = 5 a(187) = 7 a(188) = 5 a(189) = 9 a(190) = 8 a(191) = 10 a(192) = 5 a(193) = 10 a(194) = 5 a(195) = 11 a(196) = 5 a(197) = 10 a(198) = 5 a(199) = 10 a(200) = 45
On Thu, Dec 15, 2011 at 5:24 PM, Michael Kleber<michael.kleber@gmail.com>wrote:
Ah, yes, good point. That can turn into a computer search in all bases. Nice.
--Michael On Dec 15, 2011 5:09 PM, "Tom Rokicki"<rokicki@gmail.com> wrote:
Only considering the last four digits, for all values of i between 0 and 10000 not divisible by 10, shows 125 at 72 as the highest (next best is 3375 at 56).
This proves that the limit is k=72 at 125, and there is no solution that does not end in "0125" that is not 125 itself.
On Thu, Dec 15, 2011 at 1:43 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Does someone have a proof for k=72 (in decimal)? Sure seems right, but I don't think we've seen an upper bound on the x that attains the maximum k, which would justify computer-based evidence.
--Michael
On Thu, Dec 15, 2011 at 4:15 PM, N. J. A. Sloane< njas@research.att.com wrote:
> It is 72, I think, for x = 125 Yes, you are right. It seems likely that 72 should suffice for all integers x.
What about the sequence: a(n) = smallest k such that ... ? With a(125) = 72. Could you please submit it? (With keyword "base", of course) Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
All confirmed. On Thu, Dec 15, 2011 at 2:25 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Confirmations appreciated.
a(1) = 10 a(2) = 45 a(3) = 10 a(4) = 23 a(5) = 18 a(6) = 15 a(7) = 10 a(8) = 12 a(9) = 10 a(10) = 9 a(11) = 10 a(12) = 13 a(13) = 8 a(14) = 17 a(15) = 12 a(16) = 16 a(17) = 7 a(18) = 5 a(19) = 10 a(20) = 45 a(21) = 9 a(22) = 9 a(23) = 9 a(24) = 19 a(25) = 36 a(26) = 15 a(27) = 7 a(28) = 17 a(29) = 7 a(30) = 9 a(31) = 10 a(32) = 18 a(33) = 10 a(34) = 27 a(35) = 16 a(36) = 11 a(37) = 10 a(38) = 5 a(39) = 10 a(40) = 23 a(41) = 9 a(42) = 9 a(43) = 7 a(44) = 9 a(45) = 8 a(46) = 11 a(47) = 10 a(48) = 12 a(49) = 10 a(50) = 18 a(51) = 9 a(52) = 18 a(53) = 8 a(54) = 11 a(55) = 9 a(56) = 12 a(57) = 10 a(58) = 5 a(59) = 10 a(60) = 15 a(61) = 9 a(62) = 9 a(63) = 8 a(64) = 9 a(65) = 11 a(66) = 11 a(67) = 7 a(68) = 14 a(69) = 5 a(70) = 8 a(71) = 10 a(72) = 11 a(73) = 10 a(74) = 7 a(75) = 12 a(76) = 12 a(77) = 7 a(78) = 5 a(79) = 10 a(80) = 12 a(81) = 9 a(82) = 7 a(83) = 10 a(84) = 11 a(85) = 8 a(86) = 11 a(87) = 7 a(88) = 9 a(89) = 9 a(90) = 5 a(91) = 10 a(92) = 6 a(93) = 10 a(94) = 6 a(95) = 7 a(96) = 6 a(97) = 10 a(98) = 8 a(99) = 10 a(100) = 9 a(101) = 9 a(102) = 9 a(103) = 7 a(104) = 9 a(105) = 9 a(106) = 9 a(107) = 7 a(108) = 9 a(109) = 5 a(110) = 9 a(111) = 10 a(112) = 8 a(113) = 8 a(114) = 7 a(115) = 7 a(116) = 11 a(117) = 7 a(118) = 5 a(119) = 9 a(120) = 13 a(121) = 8 a(122) = 8 a(123) = 9 a(124) = 19 a(125) = 72 a(126) = 15 a(127) = 7 a(128) = 7 a(129) = 7 a(130) = 8 a(131) = 8 a(132) = 6 a(133) = 8 a(134) = 7 a(135) = 7 a(136) = 7 a(137) = 8 a(138) = 5 a(139) = 10 a(140) = 17 a(141) = 7 a(142) = 8 a(143) = 7 a(144) = 9 a(145) = 8 a(146) = 5 a(147) = 8 a(148) = 7 a(149) = 7 a(150) = 12 a(151) = 8 a(152) = 6 a(153) = 6 a(154) = 6 a(155) = 7 a(156) = 6 a(157) = 7 a(158) = 5 a(159) = 10 a(160) = 16 a(161) = 7 a(162) = 9 a(163) = 8 a(164) = 9 a(165) = 15 a(166) = 33 a(167) = 7 a(168) = 19 a(169) = 8 a(170) = 7 a(171) = 7 a(172) = 11 a(173) = 6 a(174) = 5 a(175) = 15 a(176) = 11 a(177) = 7 a(178) = 5 a(179) = 7 a(180) = 5 a(181) = 5 a(182) = 5 a(183) = 6 a(184) = 5 a(185) = 9 a(186) = 5 a(187) = 7 a(188) = 5 a(189) = 9 a(190) = 8 a(191) = 10 a(192) = 5 a(193) = 10 a(194) = 5 a(195) = 11 a(196) = 5 a(197) = 10 a(198) = 5 a(199) = 10 a(200) = 45
On Thu, Dec 15, 2011 at 5:24 PM, Michael Kleber <michael.kleber@gmail.com>wrote:
Ah, yes, good point. That can turn into a computer search in all bases. Nice.
--Michael On Dec 15, 2011 5:09 PM, "Tom Rokicki" <rokicki@gmail.com> wrote:
Only considering the last four digits, for all values of i between 0 and 10000 not divisible by 10, shows 125 at 72 as the highest (next best is 3375 at 56).
This proves that the limit is k=72 at 125, and there is no solution that does not end in "0125" that is not 125 itself.
On Thu, Dec 15, 2011 at 1:43 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Does someone have a proof for k=72 (in decimal)? Sure seems right, but I don't think we've seen an upper bound on the x that attains the maximum k, which would justify computer-based evidence.
--Michael
On Thu, Dec 15, 2011 at 4:15 PM, N. J. A. Sloane < njas@research.att.com wrote:
> It is 72, I think, for x = 125 Yes, you are right. It seems likely that 72 should suffice for all integers x.
What about the sequence: a(n) = smallest k such that ... ? With a(125) = 72. Could you please submit it? (With keyword "base", of course) Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Thank you. By the way, the smallest x with a(x) = 4 is 266. The smallest x with a(x) = 3 is 1692. And a(13485) is the first occurrence of 2. (13485; 26970. Neat.) I didn't search exhaustively, but it seems obvious that a(1023456789) is the first 1. On Thu, Dec 15, 2011 at 5:32 PM, Tom Rokicki <rokicki@gmail.com> wrote:
All confirmed.
Okay, different bases. If the base is prime p, high value is clearly p; any value 1..p-1 will take that long to give a "0", and will generate all other digits before then. For base 4, I get 6 (3x2) from initial value 2=(4/2). For base 6, I get 20 (5x4) from initial value 13_6=(36/4) (_6 means written in base 6). For base 8, I get 28 (7x4) from 2 (8/2) For base 9, I get 24 (8x3) from 3 (9/3). For base 10, I get 72 (9x8) from 125 (1000/8). For base 12, I get 99 (11x9) from 14_12 (144/9). -tom On Thu, Dec 15, 2011 at 2:51 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Thank you. By the way, the smallest x with a(x) = 4 is 266. The smallest x with a(x) = 3 is 1692. And a(13485) is the first occurrence of 2. (13485; 26970. Neat.)
I didn't search exhaustively, but it seems obvious that a(1023456789) is the first 1.
On Thu, Dec 15, 2011 at 5:32 PM, Tom Rokicki <rokicki@gmail.com> wrote:
All confirmed.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Tom Rokicki:
Okay, different bases.
I ran this earlier just by checking all x up to a million in the given base. If a million is high enough, then the k's are good... base {x,k} 04 {2,6} 06 {9,20} 08 {2,28} 09 {3,24} 10 {125,72} 12 {16,99} 14 {343,104} 15 {25,126} 16 {2,120} 18 {6561,272} 20 {25,304} 21 {49,180} 22 {14641,336} 24 {32,414} 25 {5,120} 26 {28561,400} 27 {3,234} 28 {49,432} 30 {1000,783} 32 {2,496} 33 {1331,864} 34 {2,561} 35 {49,850} 36 {1458,1120} 38 {2,703} 39 {2197,1026} 40 {50,1248} 42 {49,1476} 44 {2662,1376} 45 {75,1188} 46 {2,1035} 48 {64,1692} 49 {7,336} 50 {3125,1960} 51 {4913,1350} 52 {4394,1632} 54 {177147,2544} 55 {121,1350} 56 {64,2695} 57 {6859,1512} 58 {2,1653} 60 {4000,3186} 62 {2,1891} 63 {81,3038} 64 {2,2016} 65 {169,1600} 66 {5324,3510} 68 {4913,4288} 69 {12167,1836} 70 {6125,3864} 72 {81,4544} 74 {2,2701} 75 {125,3330}
I can confirm that Hans's numbers below through k=25 are correct, by using the check-the-last-d-digits trick that Tom Rokicki pointed out yesterday. For bases 4, 8, 9, 16, 25 it suffices to check the bottom 2 digits. For bases 6, 12, 15, 20, 21, 24 it suffices to check the bottom 3 digits. For bases 10, 14 it suffices to check the bottom 4 digits. For bases 18, 22 it suffices to check the bottom 5 digits. (Base 26 is working through 5-digit suffixes now.) --Michael On Thu, Dec 15, 2011 at 7:22 PM, Hans Havermann <gladhobo@teksavvy.com>wrote:
Tom Rokicki:
Okay, different bases.
I ran this earlier just by checking all x up to a million in the given base. If a million is high enough, then the k's are good...
base {x,k}
04 {2,6} 06 {9,20} 08 {2,28} 09 {3,24} 10 {125,72} 12 {16,99} 14 {343,104} 15 {25,126} 16 {2,120} 18 {6561,272} 20 {25,304} 21 {49,180} 22 {14641,336} 24 {32,414} 25 {5,120} 26 {28561,400} 27 {3,234} 28 {49,432} 30 {1000,783} 32 {2,496} 33 {1331,864} 34 {2,561} 35 {49,850} 36 {1458,1120} 38 {2,703} 39 {2197,1026} 40 {50,1248} 42 {49,1476} 44 {2662,1376} 45 {75,1188} 46 {2,1035} 48 {64,1692} 49 {7,336} 50 {3125,1960} 51 {4913,1350} 52 {4394,1632} 54 {177147,2544} 55 {121,1350} 56 {64,2695} 57 {6859,1512} 58 {2,1653} 60 {4000,3186} 62 {2,1891} 63 {81,3038} 64 {2,2016} 65 {169,1600} 66 {5324,3510} 68 {4913,4288} 69 {12167,1836} 70 {6125,3864} 72 {81,4544} 74 {2,2701} 75 {125,3330}
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
-- Forewarned is worth an octopus in the bush.
For base 26, 5 digits works, and the result of 400 @ 28561 agrees with Hans's numbers. Base 27, two digits suffice, result of 234 using 3. Base 28, three digits, high is 432 using 49. I need to make my program smarter at this point. On Fri, Dec 16, 2011 at 10:27 AM, Michael Kleber <michael.kleber@gmail.com> wrote:
I can confirm that Hans's numbers below through k=25 are correct, by using the check-the-last-d-digits trick that Tom Rokicki pointed out yesterday.
For bases 4, 8, 9, 16, 25 it suffices to check the bottom 2 digits. For bases 6, 12, 15, 20, 21, 24 it suffices to check the bottom 3 digits. For bases 10, 14 it suffices to check the bottom 4 digits. For bases 18, 22 it suffices to check the bottom 5 digits.
(Base 26 is working through 5-digit suffixes now.)
--Michael
On Thu, Dec 15, 2011 at 7:22 PM, Hans Havermann <gladhobo@teksavvy.com>wrote:
Tom Rokicki:
Okay, different bases.
I ran this earlier just by checking all x up to a million in the given base. If a million is high enough, then the k's are good...
base {x,k}
04 {2,6} 06 {9,20} 08 {2,28} 09 {3,24} 10 {125,72} 12 {16,99} 14 {343,104} 15 {25,126} 16 {2,120} 18 {6561,272} 20 {25,304} 21 {49,180} 22 {14641,336} 24 {32,414} 25 {5,120} 26 {28561,400} 27 {3,234} 28 {49,432} 30 {1000,783} 32 {2,496} 33 {1331,864} 34 {2,561} 35 {49,850} 36 {1458,1120} 38 {2,703} 39 {2197,1026} 40 {50,1248} 42 {49,1476} 44 {2662,1376} 45 {75,1188} 46 {2,1035} 48 {64,1692} 49 {7,336} 50 {3125,1960} 51 {4913,1350} 52 {4394,1632} 54 {177147,2544} 55 {121,1350} 56 {64,2695} 57 {6859,1512} 58 {2,1653} 60 {4000,3186} 62 {2,1891} 63 {81,3038} 64 {2,2016} 65 {169,1600} 66 {5324,3510} 68 {4913,4288} 69 {12167,1836} 70 {6125,3864} 72 {81,4544} 74 {2,2701} 75 {125,3330}
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Okay, new higher results: base 34: high is 1056 from 1419857 base 38: high is 1184 from 2476099 On Thu, Dec 15, 2011 at 4:22 PM, Hans Havermann <gladhobo@teksavvy.com> wrote:
Tom Rokicki:
Okay, different bases.
I ran this earlier just by checking all x up to a million in the given base. If a million is high enough, then the k's are good...
base {x,k}
04 {2,6} 06 {9,20} 08 {2,28} 09 {3,24} 10 {125,72} 12 {16,99} 14 {343,104} 15 {25,126} 16 {2,120} 18 {6561,272} 20 {25,304} 21 {49,180} 22 {14641,336} 24 {32,414} 25 {5,120} 26 {28561,400} 27 {3,234} 28 {49,432} 30 {1000,783} 32 {2,496} 33 {1331,864} 34 {2,561} 35 {49,850} 36 {1458,1120} 38 {2,703} 39 {2197,1026} 40 {50,1248} 42 {49,1476} 44 {2662,1376} 45 {75,1188} 46 {2,1035} 48 {64,1692} 49 {7,336} 50 {3125,1960} 51 {4913,1350} 52 {4394,1632} 54 {177147,2544} 55 {121,1350} 56 {64,2695} 57 {6859,1512} 58 {2,1653} 60 {4000,3186} 62 {2,1891} 63 {81,3038} 64 {2,2016} 65 {169,1600} 66 {5324,3510} 68 {4913,4288} 69 {12167,1836} 70 {6125,3864} 72 {81,4544} 74 {2,2701} 75 {125,3330}
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
On Fri, Dec 16, 2011 at 11:13 AM, Tom Rokicki <rokicki@gmail.com> wrote:
Okay, new higher results:
base 34: high is 1056 from 1419857 base 38: high is 1184 from 2476099
base 46: high is 1440 from 6436343 base 58: high is 1824 from 20511149 base 62: high is 1952 from 28629151 Clearly bases of twice primes permit high values. All the values (for k) are divisible by (b-1).
On 12/16/2011 3:57 PM, Tom Rokicki wrote:
On Fri, Dec 16, 2011 at 11:13 AM, Tom Rokicki<rokicki@gmail.com> wrote:
Okay, new higher results:
base 34: high is 1056 from 1419857 base 38: high is 1184 from 2476099
base 46: high is 1440 from 6436343 base 58: high is 1824 from 20511149 base 62: high is 1952 from 28629151
Clearly bases of twice primes permit high values. All the values (for k) are divisible by (b-1).
1419857 = 17^5 2476099 = 19^5 6436343 = 23^5 20511149 = 29^5 28629151 = 31^5 But for base 26, it was 28561 = 13^4. Hmm. -- Fred W. Helenius fheleni@emory.edu
I suspect the value for the highest k given base 2*p might be p^ceil(log_2(p)) On Fri, Dec 16, 2011 at 1:11 PM, Fred W. Helenius <fredh@ix.netcom.com> wrote:
On 12/16/2011 3:57 PM, Tom Rokicki wrote:
On Fri, Dec 16, 2011 at 11:13 AM, Tom Rokicki<rokicki@gmail.com> wrote:
Okay, new higher results:
base 34: high is 1056 from 1419857 base 38: high is 1184 from 2476099
base 46: high is 1440 from 6436343 base 58: high is 1824 from 20511149 base 62: high is 1952 from 28629151
Clearly bases of twice primes permit high values. All the values (for k) are divisible by (b-1).
1419857 = 17^5 2476099 = 19^5 6436343 = 23^5 20511149 = 29^5 28629151 = 31^5
But for base 26, it was 28561 = 13^4. Hmm.
-- Fred W. Helenius fheleni@emory.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Okay, I've run through b=237; results are at http://tomas.rokicki.com/k.txt In all cases, k<b^2 (although sometimes just barely). Clearly, k<b^2; just print x, and watch the digit column just to the left of the most significant digit of x. As you add x each time, you'll get a carry there or not; you will get a carry at least once every 1/k times, and after k such carries you'll have seen all the digits. -tom
Tom Rokicki:
In all cases, k<b^2 (although sometimes just barely).
Using Tom's data (now up to base 542), I've graphed the 541 {b,k} and added the b^2 curve: http://chesswanks.com/num/k.png
The graph suggests that bases fall into families characterized by k/b. On Sat, Dec 17, 2011 at 6:16 PM, Hans Havermann <gladhobo@teksavvy.com>wrote:
Tom Rokicki:
In all cases, k<b^2 (although sometimes just barely).
Using Tom's data (now up to base 542), I've graphed the 541 {b,k} and added the b^2 curve:
http://chesswanks.com/num/k.**png <http://chesswanks.com/num/k.png>
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
Allan Wechsler:
The graph suggests that bases fall into families characterized by k/b.
In prime bases, k=b. In others, k appears to be divisible by b-1. Conjecture: If the prime factorization of composite b is p1^e1 * p2^e2 * p3^e3 * ..., then the factorization of k/(b-1), and x also, are each a product of powers of primes that are a subset of {p1, p2, p3, ...}.
In prime bases, k=b. In others, k appears to be divisible by b-1. Conjecture: If the prime factorization of composite b is p1^e1 * p2^e2 * p3^e3 * ..., then the factorization of k/(b-1), and x also, are each a product of powers of primes that are a subset of {p1, p2, p3, ...}.
I'll make this somewhat stronger: If the prime factorization of composite b is p_1^e_1 * p_2^e_2 * ... * p_n^e_n, then the factorization of x*k/(b-1) is p_1^f_1 * p_2^f_2 * ... * p_n^f_n. If e_1=e_2=...=e_n, then f_1=f_2=...=f_n. Since Tom Rokicki had multiple x's for some bases in his list < http://tomas.rokicki.com/k.txt >, I should clarify that I take x to be the *smallest* number that yields k. Special case 1: b = p^e, e>1 -> x = p and k/(b-1) = p^(e-1) Special case 2: b = p*q, q>p -> x = q^ceil(log_p(q)) and k/(b-1) = p^ceil(log_p(q)) (This is just a guessed extension of Tom Rokicki's formulation provided on December 16.) I've been looking at b = p*q*r, r>q>p. There are two difficulties: What is the exponent (f) of x*k/(b-1) and how does one determine the separation of x*k/(b-1) into its components x and k/(b-1)? base b-factored x*k/(b-1) x k/(b-1) 030 2*3*5 2^3*3^3*5^3 2^3*5^3 3^3 042 2*3*7 2^2*3^2*7^2 7^2 2^2*3^2 066 2*3*11 2^6*3^6*11^6 3^6*11^6 2^6 070 2*5*7 2^6*5^6*7^6 5^6*7^6 2^6 078 2*3*13 2^3*3^3*13^3 3*13^3 2^3*3^2 102 2*3*17 2^5*3^5*17^5 3^4*17^5 2^5*3 105 3*5*7 3^4*5^4*7^4 5^4*7^4 3^4 110 2*5*11 2^2*5^2*11^2 11^2 2^2*5^2 114 2*3*19 2^3*3^3*19^3 2*19^3 2^2*3^3 130 2*5*13 2^7*5^7*13^7 5^7*13^7 2^7 138 2*3*23 2^7*3^7*23^7 3^7*23^7 2^7 154 2*7*11 2^7*7^7*11^7 7^7*11^7 2^7 165 3*5*11 3^3*5^3*11^3 5^2*11^3 3^3*5 170 2*5*17 2^5*5^5*17^5 5^4*17^5 2^5*5 174 2*3*29 2^4*3^4*29^4 2^3*29^4 2*3^4 182 2*7*13 2^2*7^2*13^2 2^2*7^2 13^2 186 2*3*31 2^4*3^4*31^4 2^3*31^4 2*3^4 190 2*5*19 2^5*5^5*19^5 5^4*19^5 2^5*5 195 3*5*13 3^2*5^2*13^2 3^2*5^2 13^2 222 2*3*37 2^3*3^3*37^3 37^3 2^3*3^3 230 2*5*23 2^3*5^3*23^3 5*23^3 2^3*5^2 231 3*7*11 3^3*7^3*11^3 7^2*11^3 3^3*7 238 2*7*17 2^5*7^5*17^5 7^4*17^5 2^5*7 246 2*3*41 2^5*3^5*41^5 2^5*41^5 3^5 255 3*5*17 3^5*5^5*17^5 5^5*17^5 3^5 258 2*3*43 2^8*3^8*43^8 3^8*43^8 2^8 266 2*7*19 2^8*7^8*19^8 7^8*19^8 2^8 273 3*7*13 3^5*7^5*13^5 7^5*13^5 3^5 282 2*3*47 2^8*3^8*47^8 3^8*47^8 2^8 285 3*5*19 3^5*5^5*19^5 5^5*19^5 3^5 286 2*11*13 2^8*11^8*13^8 11^8*13^8 2^8 290 2*5*29 2^8*5^8*29^8 5^8*29^8 2^8 310 2*5*31 2^8*5^8*31^8 5^8*31^8 2^8 318 2*3*53 2^5*3^5*53^5 3^3*53^5 2^5*3^2 322 2*7*23 2^8*7^8*23^8 7^8*23^8 2^8 345 3*5*23 3^5*5^5*23^5 5^5*23^5 3^5 354 2*3*59 2^4*3^4*59^4 2^2*59^4 2^2*3^4 357 3*7*17 3^3*7^3*17^3 3^3*17^3 7^3 366 2*3*61 2^4*3^4*61^4 2^2*61^4 2^2*3^4 370 2*5*37 2^6*5^6*37^6 5^5*37^6 2^6*5 374 2*11*17 2^5*11^5*17^5 11^4*17^5 2^5*11 385 5*7*11 5^3*7^3*11^3 5^3*11^3 7^3 399 3*7*19 3^2*7^2*19^2 3^2*7^2 19^2 402 2*3*67 2^7*3^7*67^7 3^6*67^7 2^7*3 406 2*7*29 2^3*7^3*29^3 7*29^3 2^3*7^2 410 2*5*41 2^4*5^4*41^4 5^2*41^4 2^4*5^2 418 2*11*19 2^2*11^2*19^2 2^2*11^2 19^2 426 2*3*71 2^7*3^7*71^7 3^6*71^7 2^7*3 429 3*11*13 3^2*11^2*13^2 3*13^2 3*11^2 430 2*5*43 2^4*5^4*43^4 5^2*43^4 2^4*5^2 434 2*7*31 2^3*7^3*31^3 7*31^3 2^3*7^2 435 3*5*29 3^4*5^4*29^4 5^3*29^4 3^4*5 438 2*3*73 2^4*3^4*73^4 3*73^4 2^4*3^3 442 2*13*17 2^5*13^5*17^5 13^4*17^5 2^5*13 455 5*7*13 5^3*7^3*13^3 5^3*13^3 7^3 465 3*5*31 3^4*5^4*31^4 5^3*31^4 3^4*5 470 2*5*47 2^4*5^4*47^4 5^2*47^4 2^4*5^2 474 2*3*79 2^4*3^4*79^4 3*79^4 2^4*3^3 483 3*7*23 3^2*7^2*23^2 23^2 3^2*7^2 494 2*13*19 2^5*13^5*19^5 13^4*19^5 2^5*13 498 2*3*83 2^5*3^5*83^5 2^4*83^5 2*3^5 506 2*11*23 2^2*11^2*23^2 23^2 2^2*11^2 518 2*7*37 2^9*7^9*37^9 7^9*37^9 2^9 530 2*5*53 2^9*5^9*53^9 5^9*53^9 2^9 534 2*3*89 2^9*3^9*89^9 3^9*89^9 2^9
Tom's list < http://tomas.rokicki.com/k.txt > of {base, k, x1, x2, ...} is now complete to base 1025. I've updated my graph < http://chesswanks.com/num/k.png
accordingly. The minimum base with k > 10^6 is now known to be base 1010, wherein the number x = 1030301 (digits: {1,10,101}) requires k = 1009000 multiplications (x, 2x, 3x, ..., 1009000x) to manifest all 1010 digits: The digit 1009 does not appear in any of {x, 2x, 3x, ..., 1008999x}, but 1009000*{1,10,101} = {1009,0,0,0}.
Special case 1: b = p^e, e>1 -> x = p and k/(b-1) = p^(e-1)
b = p^e appears to be the largest of a family of bases whose k/(b-1) = p^(e-1). The others are greater than p^(e-1) and divisible by p. I've labelled four of these families in my graph: k/(b-1) = 3^6: b = {732, 735, 738, 741, 744, 747, 750, 753, 756, 759, 762, 765, 768, 771, 777, 783, 789, 795, 801, 807, 813, 819, 825, 831, 837, 843, 849, 855, 861, 867, 873, 879, 885, 891, 897, 903, 909, 915, 921, 927, 933, 939, 951, 963, 981, 987, 993, 999, 1005, 1011, 1017, ...}, presumably not complete until we get to base 2187 = 3^7. k/(b-1) = 5^4: b = {630, 635, 640, 645, 655, 665, 675, 685, 695, 715, 725, 745, 755, 775, 785, 805, 815, 835, 845, 865, 875, 895, 905, 925, 935, 955, 965, 985, 995, 1025, ...}, presumably not complete until we get to base 3125 = 5^5. k/(b-1) = 2^9: b = {514, 516, 518, 520, 522, 524, 526, 528, 530, 532, 534, 536, 538, 540, 542, 544, 546, 548, 550, 554, 556, 558, 560, 562, 564, 566, 568, 572, 574, 576, 580, 584, 586, 590, 592, 596, 602, 604, 608, 610, 614, 620, 622, 626, 628, 632, 634, 638, 652, 656, 658, 662, 664, 668, 674, 676, 682, 686, 688, 692, 694, 698, 704, 706, 712, 716, 718, 724, 734, 746, 752, 758, 764, 766, 772, 776, 778, 788, 794, 796, 802, 808, 818, 824, 838, 842, 844, 848, 856, 862, 866, 872, 878, 886, 892, 898, 904, 908, 914, 916, 922, 926, 932, 934, 944, 956, 958, 964, 974, 976, 982, 998, 1004, 1006, 1016, 1018, 1024}, presumably complete because 1024 = 2^10. k/(b-1) = 7^3: b = {350, 357, 364, 371, 378, 385, 392, 413, 427, 441, 455, 469, 497, 511, 539, 553, 581, 623, 637, 679, 707, 721, 749, 763, 791, 833, 889, 917, 959, 973, ...}, presumably not complete until we get to base 2401 = 7^4.
I think I can also see the family for 2^8 = 256 (ending at 2^9 = 512), just above the marked-but-not-labeled family for 3^5 = 243 (ending at 3^6 = 729). Between that and 7^3 I can see a sparse family that I conjecture is the one for 17^2 = 289. Just above 7^3 = 343, there's another sparse family that might pertain to 19^2 = 361. If we plotted k/(b-1) rather than k itself, the families would be horizontal lines and I suspect things might be clearer. On Wed, Dec 21, 2011 at 10:47 AM, Hans Havermann <gladhobo@teksavvy.com>wrote:
Special case 1: b = p^e, e>1 -> x = p and k/(b-1) = p^(e-1)
b = p^e appears to be the largest of a family of bases whose k/(b-1) = p^(e-1). The others are greater than p^(e-1) and divisible by p. I've labelled four of these families in my graph:
k/(b-1) = 3^6: b = {732, 735, 738, 741, 744, 747, 750, 753, 756, 759, 762, 765, 768, 771, 777, 783, 789, 795, 801, 807, 813, 819, 825, 831, 837, 843, 849, 855, 861, 867, 873, 879, 885, 891, 897, 903, 909, 915, 921, 927, 933, 939, 951, 963, 981, 987, 993, 999, 1005, 1011, 1017, ...}, presumably not complete until we get to base 2187 = 3^7.
k/(b-1) = 5^4: b = {630, 635, 640, 645, 655, 665, 675, 685, 695, 715, 725, 745, 755, 775, 785, 805, 815, 835, 845, 865, 875, 895, 905, 925, 935, 955, 965, 985, 995, 1025, ...}, presumably not complete until we get to base 3125 = 5^5.
k/(b-1) = 2^9: b = {514, 516, 518, 520, 522, 524, 526, 528, 530, 532, 534, 536, 538, 540, 542, 544, 546, 548, 550, 554, 556, 558, 560, 562, 564, 566, 568, 572, 574, 576, 580, 584, 586, 590, 592, 596, 602, 604, 608, 610, 614, 620, 622, 626, 628, 632, 634, 638, 652, 656, 658, 662, 664, 668, 674, 676, 682, 686, 688, 692, 694, 698, 704, 706, 712, 716, 718, 724, 734, 746, 752, 758, 764, 766, 772, 776, 778, 788, 794, 796, 802, 808, 818, 824, 838, 842, 844, 848, 856, 862, 866, 872, 878, 886, 892, 898, 904, 908, 914, 916, 922, 926, 932, 934, 944, 956, 958, 964, 974, 976, 982, 998, 1004, 1006, 1016, 1018, 1024}, presumably complete because 1024 = 2^10.
k/(b-1) = 7^3: b = {350, 357, 364, 371, 378, 385, 392, 413, 427, 441, 455, 469, 497, 511, 539, 553, 581, 623, 637, 679, 707, 721, 749, 763, 791, 833, 889, 917, 959, 973, ...}, presumably not complete until we get to base 2401 = 7^4.
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
Allan Wechsler:
If we plotted k/(b-1) rather than k itself, the families would be horizontal lines and I suspect things might be clearer.
http://chesswanks.com/num/k-reduced.png I'll sort/label all the families eventually: They aren't all simple powers. In the meantime, I'm hoping someone might figure out why the 'missing' base values in each family allow for larger k.
The new graph is very pretty, thank you! I like spotting things like the 121/125/128 cluster (11^2, 5^3, 2^7) On Wed, Dec 21, 2011 at 1:32 PM, Hans Havermann <gladhobo@teksavvy.com>wrote:
I'll sort/label all the families eventually
http://chesswanks.com/num/k-**reduced.families.txt<http://chesswanks.com/num/k-reduced.families.txt>
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
Wilson's puzzle: Given a base b and initial nonnegative integer seed x, define k(b,x) to be the smallest value k such that the base-b representations of (1*x, 2*x, 3*x, ..., k*x) use all of the b digits. Define k(b) to be the largest value of k for all x. The following are true. k(p), for p prime, is p. (A seed value of 1 suffices, and, ignoring multiples of p and just looking at the least significant digit, no other value will generate a higher result.) k(b) <= b(b-1). (Look at the digit place one greater than the least significant digit of the best seed 'x'; by the time b(b-1)*x is reached, this digit has progressed through 1 all the way to b-1. The zero is covered at the time we multiplied x by b.) For all values of nonnegative t, 1<t<b and positive n where b^n/t is an integer, we have k(b,b^n/t)=t*(b-1) (1) In order for b^n/t to be an integer, the set of prime divisors of t must be a (strict or non-strict) subset of the set of prime divisors of b. The highest k for all allowed values of t occurs for the greatest such value of t; it is easy to show such a value of t must be >= sqrt(b). We can show (1) by considering the base-b expansion of 1/t. The last digit encountered will always be b-1. We perform long division of b^n by t in base b. At every point our remainder r<t, and the next digit is floor(rb/t). We can prove that rb/t < b-1 as follows, using the fact that r<t<b, and t and b are nonnegative integers: rb/t < b-1 rb < (b-1)t t < (b-r)b Now, b>r so b-r >=1, and thus (b-r)b >= b, and b > t, so we are done. Consider next all values of i from 0..t-1. For all such values of i when computing the decimal expansion of i/t, we will never encounter the digit b-1. But at the value of i=t, we calculate 1.0, so t..2t-1 will generate the same digits as 0..t-1, except maybe also including a 1. The first time we will encounter digit b-1 is at i=(b-1)t, so k(b,x)=t*(b-1) Empirically, it appears that there is no higher seed possible; that is, that k(b)=k(b,x). I have examined values of b up to 1600 without finding a counterexample. I believe this can be proved but have not yet been able to prove it. If it is true, then for non-prime base b, the limit on k(b) is (b-1)(b-2) (t and b must have at least one common factor, and thus they must not be adjacent, so t<=b-2), and this is attained for 2+2^n for n>0. Interestingly, the case we started with, b=10 or decimal, is one of those values at the limit.
In our previous email we proved that, for non-prime b, k(b,b^n/t)=t*(b-1) (1<t<b, b^n/t integer) We showed this value is maximized when t is the largest value less than b, that does not contain a prime factor not contained also in b. We surmised that this is the maximum attainable value for k(b). We prove this here. Consider an arbitrary nonnegative integer x. Assume b not prime. Assume x%b > 0 (because for non-prime b, k(b,x)==k(b,x*b)). For a given n, define T(x,n)={xi%b^n|i integer >=0}, and define t(x,n)=|T(x,n)|. Clearly t(x,n) = b^n/gcd(x%b^n, b^n). T(x,n) is the number of distinct values (xi%b^n) can take on; these values are exactly the 0 point, plus the points needed to break the interval (0..b^n) into equal pieces. If t(x,n)>=b, then the digit at position n-1 of these distinct values includes all the values from {0..b-1}; otherwise, at least the value b-1 is omitted. For the given value x, let n be the largest value for which t(x,i)<b, 0<=i<=n. n=0 always works, so there will always be such a value. This is our demarcation point. Define a=floor(x/b^n)%b^n (the digit above the demarcation point). Define t=t(x,n). Define c=(x%b^n)/t. Note that 1<=c<t<b, and gcd(c,b)=1. We already know that, since b^n/t is an integer and 1<t<b, that k(b,b^n/t)=t*(b-1). Since this is always greater than b for non-prime b, we can ignore the digit 0 and thus dispense with any concern for dropping the leading digits, since the 0 will always be handled by the least significant digit of x*b. We will prove that k(b,x)<=t*(b-1). Indeed, we show that the digit to the left of the demarcation point, alone, will see all digit values within that span. There are t(x,n+1) possible values at digit position n. By definition of the demarcation point, this is >=b, and these values are evenly distributed. Let us calculate t(x,n+1). The n low-order digits of the values in T(x,n+1) are clearly just those permitted by T(x,n); there are t such values. In addition there are b possible values for digit position n in T(x,n+1), so we know t(x,n+1)<=t*b. We also know that the first t(x,n+1) values for (xi%b^{n+1}) (for i=0..t(x,n+1)) generate the same set as T(x,n+1) because t(x,n+1)*x evenly divides b^{n+1}. The values (xi%b&{n+1}) for 0..t*(b-1) will either cover the set T(x,n+1) completely (in the case where t(x,n+1)<t*b), or cover all but t-1 of the points from T(x,n+1). Since the values in T(x,n+1) are uniformly distributed and, if t(x,n+1)=t*b, there are exactly t values for each possible most significant digit, this means we must have covered all of the digits at least once. Thus, k(b,x) <= k(b,b^n/t) = t*(b-1). This proves that k(b) is k(b,b^n/t) = t*(b-1), where t is the largest value less than b that does not contain a prime factor that is not also in b. This solves Wilson's puzzle for non-prime b. We've already solved it for prime p, so this completes the solution. (I've tested this against known results through b=3900 and it holds up.)
To reiterate the problem: For base b >= 2, to find the least k(b) such that for any x >= 1, the values {x, 2x, ..., kx} written in base-b together must include all the base-b digits. Tom Rokicki gives the following solution (I assume his proof is good, I did not check it thoroughly): k(b) = b, if b is prime (b-1)*A079277(n), otherwise. I confirmed that this seems to match brute-force computations for small b. But then I became interested in x(b), the smallest x that requires k(b) multiples to include every base-b digit. As an example, I originally posed the problem for base b = 10. Tom's solution gives k(10) = 72, that is, for any x >= 1, all the base-10 digits occur among the base-10 representations of {x, 2x, ..., 72x}, and 72 is necessary for some x, the smallest being x = 125, so that x(10) = 125. Assuming k(b) is correct, I tried computing x(b) (the smallest x requiring k(b)) by brute force for small b (via a C++ program), and got (for 2 <= b <= 33): 1,1,2,1,9,1,2,3,125,1,16,1,343,25,2,1,6561,1,25,49,14641,1,32,5,28561,3,49,1,1000,1,2,1331 From this sparse evidence, I conjecture that every prime divisor of x(b) is a divisor of b. x(30) = 1000 refutes the conjecture that x(b) is always a prime power. Tom Rokicki's proof gives x(p) = 1 for prime p as a corollary. I conjecture x(p^n) = p for higher prime powers. The computations for x(34) ran for more than a minute without results. So I gave up on brute force and narrowed the candidates to x(34) = 2^x*17^y based on my conjecture about the prime divisors of x(b). I was able to find x = 1419857 = 17^5 requiring k = k(34) = 1056, so we have x(34) <= 17^5, with almost certain equality. One might conjecture x(2p) = p^n with n = ceil(log2(p)) or thereabouts. If that is the case, x(2p) grows large very quickly, far beyond brute force computability (by testing each x >= 1). The x(b) prime divisor conjecture, if true, makes the search space tractable, but the sheer size of the numbers involved make it more suitable problem for Mma or such as opposed to what I have at my disposal.
Howdy! I've confirmed that, at least through base 8300 or so, the smallest x that yields the longest period is exactly that seed that is b^n/t, where t is the largest value < b with no prime divisors not also prime divisors of b. I have a cleaner proof that makes this more clear, and also shows that this is the case. If there is interest in the cleaner proof I can post it. The outline is simply: 1. Handle prime b and x ending in 0 first. Then essentially eliminate the digit 0 from consideration and only use 1..b-1 (this makes the rest slightly easier). 2. Define k(b,x,n) which is x in base b but focusing only on the lower order n digits. 3. Show k(b,x,n) where gcd(x,b^n)<b never includes the b-1 digit. 4. Show k(b,x,n) where gcd(x,b^n)>b always includes all digits at digit position n-1, and k(b,x,n) <= k(b,gcd(x,b^n),n); this lets us restrict attention to divisors of b^n when trying to find the max k. 6. Show that k(b,b^n/t)=(b-1)t when b^n/t is an integer and t<b.
From there it's clear all we need do is maximize b^n/t for t in divisors of b^n and t<b and we've got both the seed (b^n/t) and the length ((b-1)t).
The numbers do indeed get big. On Sat, Jan 7, 2012 at 9:38 AM, David Wilson <davidwwilson@comcast.net> wrote:
To reiterate the problem:
For base b >= 2, to find the least k(b) such that for any x >= 1, the values {x, 2x, ..., kx} written in base-b together must include all the base-b digits.
Tom Rokicki gives the following solution (I assume his proof is good, I did not check it thoroughly):
k(b) = b, if b is prime (b-1)*A079277(n), otherwise.
I confirmed that this seems to match brute-force computations for small b.
But then I became interested in x(b), the smallest x that requires k(b) multiples to include every base-b digit.
As an example, I originally posed the problem for base b = 10. Tom's solution gives k(10) = 72, that is, for any x >= 1, all the base-10 digits occur among the base-10 representations of {x, 2x, ..., 72x}, and 72 is necessary for some x, the smallest being x = 125, so that x(10) = 125.
Assuming k(b) is correct, I tried computing x(b) (the smallest x requiring k(b)) by brute force for small b (via a C++ program), and got (for 2 <= b <= 33):
1,1,2,1,9,1,2,3,125,1,16,1,343,25,2,1,6561,1,25,49,14641,1,32,5,28561,3,49,1,1000,1,2,1331
From this sparse evidence, I conjecture that every prime divisor of x(b) is a divisor of b. x(30) = 1000 refutes the conjecture that x(b) is always a prime power. Tom Rokicki's proof gives x(p) = 1 for prime p as a corollary. I conjecture x(p^n) = p for higher prime powers.
The computations for x(34) ran for more than a minute without results. So I gave up on brute force and narrowed the candidates to x(34) = 2^x*17^y based on my conjecture about the prime divisors of x(b). I was able to find x = 1419857 = 17^5 requiring k = k(34) = 1056, so we have x(34) <= 17^5, with almost certain equality.
One might conjecture x(2p) = p^n with n = ceil(log2(p)) or thereabouts. If that is the case, x(2p) grows large very quickly, far beyond brute force computability (by testing each x >= 1). The x(b) prime divisor conjecture, if true, makes the search space tractable, but the sheer size of the numbers involved make it more suitable problem for Mma or such as opposed to what I have at my disposal.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
Typos, sorry:
3. Show k(b,x,n) where gcd(x,b^n)<b never includes the b-1 digit. 4. Show k(b,x,n) where gcd(x,b^n)>b always includes all digits at
should be
3. Show k(b,x,n) where b^n/gcd(x,b^n)<b never includes the b-1 digit. 4. Show k(b,x,n) where b^n/gcd(x,b^n)>b always includes all digits at
Well, then, it looks like I owe Tom an apology, he apparently preceeded me in all of my conclusions. Perhaps I need to read a bit more before writing. On 1/7/2012 1:03 PM, Tom Rokicki wrote:
Typos, sorry:
3. Show k(b,x,n) where gcd(x,b^n)<b never includes the b-1 digit. 4. Show k(b,x,n) where gcd(x,b^n)>b always includes all digits at should be
3. Show k(b,x,n) where b^n/gcd(x,b^n)<b never includes the b-1 digit. 4. Show k(b,x,n) where b^n/gcd(x,b^n)>b always includes all digits at
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
More likely, I need to write more clearly and with fewer mistakes. Also I don't think I actually stated the result you have on smallest seed. So no need for any apologies. If you want to be completely correct, I owe Michael Kleber an apology for repeating something he proved, and I don't have an excuse of his writeup being unclear. On Sat, Jan 7, 2012 at 11:17 AM, David Wilson <davidwwilson@comcast.net> wrote:
Well, then, it looks like I owe Tom an apology, he apparently preceeded me in all of my conclusions. Perhaps I need to read a bit more before writing.
On 1/7/2012 1:03 PM, Tom Rokicki wrote:
Typos, sorry:
3. Show k(b,x,n) where gcd(x,b^n)<b never includes the b-1 digit. 4. Show k(b,x,n) where gcd(x,b^n)>b always includes all digits at
should be
3. Show k(b,x,n) where b^n/gcd(x,b^n)<b never includes the b-1 digit. 4. Show k(b,x,n) where b^n/gcd(x,b^n)>b always includes all digits at
_______________________________________________
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
When I posed the problem, I thought it might be an interesting diversion, but perhaps there are a couple of sequences and perhaps a paper in there. On 1/7/2012 2:49 PM, Tom Rokicki wrote:
More likely, I need to write more clearly and with fewer mistakes.
Also I don't think I actually stated the result you have on smallest seed. So no need for any apologies.
If you want to be completely correct, I owe Michael Kleber an apology for repeating something he proved, and I don't have an excuse of his writeup being unclear.
On Sat, Jan 7, 2012 at 11:17 AM, David Wilson<davidwwilson@comcast.net> wrote:
Well, then, it looks like I owe Tom an apology, he apparently preceeded me in all of my conclusions. Perhaps I need to read a bit more before writing.
On Sat, Jan 7, 2012 at 4:25 PM, David Wilson <davidwwilson@comcast.net>wrote:
When I posed the problem, I thought it might be an interesting diversion, but perhaps there are a couple of sequences and perhaps a paper in there.
I would think so! Though for a paper, it would be great to show at least a little progress on Michael Reid's question, looking for a *set* of multipliers, not necessarily of the form {1,...,k}. --Michael
On 1/7/2012 2:49 PM, Tom Rokicki wrote:
More likely, I need to write more clearly and with fewer mistakes.
Also I don't think I actually stated the result you have on smallest seed. So no need for any apologies.
If you want to be completely correct, I owe Michael Kleber an apology for repeating something he proved, and I don't have an excuse of his writeup being unclear.
On Sat, Jan 7, 2012 at 11:17 AM, David Wilson<davidwwilson@comcast.**net<davidwwilson@comcast.net>> wrote:
Well, then, it looks like I owe Tom an apology, he apparently preceeded me in all of my conclusions. Perhaps I need to read a bit more before writing.
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
-- Forewarned is worth an octopus in the bush.
On Sat, Jan 7, 2012 at 2:49 PM, Tom Rokicki <rokicki@gmail.com> wrote:
More likely, I need to write more clearly and with fewer mistakes.
Also I don't think I actually stated the result you have on smallest seed. So no need for any apologies.
If you want to be completely correct, I owe Michael Kleber an apology for repeating something he proved, and I don't have an excuse of his writeup being unclear.
Nah, you were careful enough to get b(b-1) out of it, while I only got b^2-1. I'm watching with interest, though! --Michael -- Forewarned is worth an octopus in the bush.
I'll do that. On 12/15/2011 4:15 PM, N. J. A. Sloane wrote:
What about the sequence: a(n) = smallest k such that ... ? With a(125) = 72. Could you please submit it? (With keyword "base", of course) Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Submitted as A202296. On 12/15/2011 4:15 PM, N. J. A. Sloane wrote:
It is 72, I think, for x = 125 Yes, you are right. It seems likely that 72 should suffice for all integers x. What about the sequence: a(n) = smallest k such that ... ? With a(125) = 72. Could you please submit it? (With keyword "base", of course) Neil
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (7)
-
Allan Wechsler -
David Wilson -
Fred W. Helenius -
Hans Havermann -
Michael Kleber -
N. J. A. Sloane -
Tom Rokicki