This problem was pretty super cool. It was so awesome to find that this problem at its heart was a fractal. Fractals are awesome. Elements in Pascal’s Triangle that are not divisible by a prime form a Sierpiński triangle. See the visualization below. I was hoping that I could find a nifty formula online, but was unable to. I did read and learn about the Lucas Correspondence Theorem which is only kinda applicable here. Ends up I had to roll my own formula. Being a fractal, it works recursively. I’m sure there’s some way to speed this up to eliminate the time spent in calculating the powers of 7. This program gets the solution in just under 5 minutes with Pypy3.
import math
def solve(rows):
count = 0
for n in range(rows):
sevens = n % 7 + 1
while n >= 7:
e = 7 ** int(math.log(n, 7))
sevens *= n // e + 1
n %= e
count += sevens
return count
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
1
11
111
1111
11111
111111
1111111
1 1
11 11
111 111
1111 1111
11111 11111
111111 111111
11111111111111
1 1 1
11 11 11
111 111 111
1111 1111 1111
11111 11111 11111
111111 111111 111111
111111111111111111111
1 1 1 1
11 11 11 11
111 111 111 111
1111 1111 1111 1111
11111 11111 11111 11111
111111 111111 111111 111111
1111111111111111111111111111
1 1 1 1 1
11 11 11 11 11
111 111 111 111 111
1111 1111 1111 1111 1111
11111 11111 11111 11111 11111
111111 111111 111111 111111 111111
11111111111111111111111111111111111
1 1 1 1 1 1
11 11 11 11 11 11
111 111 111 111 111 111
1111 1111 1111 1111 1111 1111
11111 11111 11111 11111 11111 11111
111111 111111 111111 111111 111111 111111
111111111111111111111111111111111111111111
1 1 1 1 1 1 1
11 11 11 11 11 11 11
111 111 111 111 111 111 111
1111 1111 1111 1111 1111 1111 1111
11111 11111 11111 11111 11111 11111 11111
111111 111111 111111 111111 111111 111111 111111
1111111111111111111111111111111111111111111111111
1 1
11 11
111 111
1111 1111
11111 11111
111111 111111
1111111 1111111
1 1 1 1
11 11 11 11
111 111 111 111
1111 1111 1111 1111
11111 11111 11111 11111
111111 111111 111111 111111
11111111111111 11111111111111
1 1 1 1 1 1
11 11 11 11 11 11
111 111 111 111 111 111
1111 1111 1111 1111 1111 1111
11111 11111 11111 11111 11111 11111
111111 111111 111111 111111 111111 111111
111111111111111111111 111111111111111111111
1 1 1 1 1 1 1 1
11 11 11 11 11 11 11 11
111 111 111 111 111 111 111 111
1111 1111 1111 1111 1111 1111 1111 1111
11111 11111 11111 11111 11111 11111 11111 11111
111111 111111 111111 111111 111111 111111 111111 111111
1111111111111111111111111111 1111111111111111111111111111
1 1 1 1 1 1 1 1 1 1
11 11 11 11 11 11 11 11 11 11
111 111 111 111 111 111 111 111 111 111
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
11111 11111 11111 11111 11111 11111 11111 11111 11111 11111
111111 111111 111111 111111 111111 111111 111111 111111 111111 111111
11111111111111111111111111111111111 11111111111111111111111111111111111
1 1 1 1 1 1 1 1 1 1 1 1
11 11 11 11 11 11 11 11 11 11 11 11
111 111 111 111 111 111 111 111 111 111 111 111
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111
111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111
111111111111111111111111111111111111111111 111111111111111111111111111111111111111111
1 1 1 1 1 1 1 1 1 1 1 1 1 1
11 11 11 11 11 11 11 11 11 11 11 11 11 11
111 111 111 111 111 111 111 111 111 111 111 111 111 111
1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111 11111
111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111 111111
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1 1 1
11 11 11
111 111 111
1111 1111 1111
11111 11111 11111
111111 111111 111111
1111111 1111111 1111111
1 1 1 1 1 1
11 11 11 11 11 11
111 111 111 111 111 111
import pytest
from problem import solve
_test_solve = (
(1, 1),
(2, 3),
(3, 6),
(4, 10),
(5, 15),
(6, 21),
(7, 28),
(8, 30),
(9, 34),
(10, 40),
(11, 48),
(12, 58),
(13, 70),
(14, 84),
(15, 87),
(16, 93),
(17, 102),
(18, 114),
(19, 129),
(20, 147),
(21, 168),
(22, 172),
(23, 180),
(24, 192),
(25, 208),
(26, 228),
(27, 252),
(28, 280),
(29, 285),
(30, 295),
(31, 310),
(32, 330),
(33, 355),
(34, 385),
(35, 420),
(36, 426),
(37, 438),
(38, 456),
(39, 480),
(40, 510),
(41, 546),
(42, 588),
(43, 595),
(44, 609),
(45, 630),
(46, 658),
(47, 693),
(48, 735),
(49, 784),
(50, 786),
(51, 790),
(52, 796),
(53, 804),
(54, 814),
(55, 826),
(56, 840),
(57, 844),
(58, 852),
(59, 864),
(60, 880),
(61, 900),
(62, 924),
(63, 952),
(64, 958),
(65, 970),
(66, 988),
(67, 1012),
(68, 1042),
(69, 1078),
(70, 1120),
(71, 1128),
(72, 1144),
(73, 1168),
(74, 1200),
(75, 1240),
(76, 1288),
(77, 1344),
(78, 1354),
(79, 1374),
(80, 1404),
(81, 1444),
(82, 1494),
(83, 1554),
(84, 1624),
(85, 1636),
(86, 1660),
(87, 1696),
(88, 1744),
(89, 1804),
(90, 1876),
(91, 1960),
(92, 1974),
(93, 2002),
(94, 2044),
(95, 2100),
(96, 2170),
(97, 2254),
(98, 2352),
(99, 2355),
(100, 2361),
(101, 2370),
(102, 2382),
(103, 2397),
(104, 2415),
(105, 2436),
(106, 2442),
(107, 2454),
(108, 2472),
(109, 2496),
(110, 2526),
(111, 2562),
(112, 2604),
(113, 2613),
(114, 2631),
(115, 2658),
(116, 2694),
(117, 2739),
(118, 2793),
(119, 2856),
(120, 2868),
(121, 2892),
(122, 2928),
(123, 2976),
(124, 3036),
(125, 3108),
(126, 3192),
(127, 3207),
(128, 3237),
(129, 3282),
(130, 3342),
(131, 3417),
(132, 3507),
(133, 3612),
(134, 3630),
(135, 3666),
(136, 3720),
(137, 3792),
(138, 3882),
(139, 3990),
(140, 4116),
(141, 4137),
(142, 4179),
(143, 4242),
(144, 4326),
(145, 4431),
(146, 4557),
(147, 4704),
(148, 4708),
(149, 4716),
(150, 4728),
(151, 4744),
(152, 4764),
(153, 4788),
(154, 4816),
(155, 4824),
(156, 4840),
(157, 4864),
(158, 4896),
(159, 4936),
(160, 4984),
(161, 5040),
(162, 5052),
(163, 5076),
(164, 5112),
(165, 5160),
(166, 5220),
(167, 5292),
(168, 5376),
(169, 5392),
(170, 5424),
(171, 5472),
(172, 5536),
(173, 5616),
(174, 5712),
(175, 5824),
(176, 5844),
(177, 5884),
(178, 5944),
(179, 6024),
(180, 6124),
(181, 6244),
(182, 6384),
(183, 6408),
(184, 6456),
(185, 6528),
(186, 6624),
(187, 6744),
(188, 6888),
(189, 7056),
(190, 7084),
(191, 7140),
(192, 7224),
(193, 7336),
(194, 7476),
(195, 7644),
(196, 7840),
(197, 7845),
(198, 7855),
(199, 7870),
(200, 7890),
(201, 7915),
(202, 7945),
(203, 7980),
(204, 7990),
(205, 8010),
(206, 8040),
(207, 8080),
(208, 8130),
(209, 8190),
(210, 8260),
(211, 8275),
(212, 8305),
(213, 8350),
(214, 8410),
(215, 8485),
(216, 8575),
(217, 8680),
(218, 8700),
(219, 8740),
(220, 8800),
(221, 8880),
(222, 8980),
(223, 9100),
(224, 9240),
(225, 9265),
(226, 9315),
(227, 9390),
(228, 9490),
(229, 9615),
(230, 9765),
(231, 9940),
(232, 9970),
(233, 10030),
(234, 10120),
(235, 10240),
(236, 10390),
(237, 10570),
(238, 10780),
(239, 10815),
(240, 10885),
(241, 10990),
(242, 11130),
(243, 11305),
(244, 11515),
(245, 11760),
(246, 11766),
(247, 11778),
(248, 11796),
(249, 11820),
(250, 11850),
(251, 11886),
(252, 11928),
(253, 11940),
(254, 11964),
(255, 12000),
(256, 12048),
(257, 12108),
(258, 12180),
(259, 12264),
(260, 12282),
(261, 12318),
(262, 12372),
(263, 12444),
(264, 12534),
(265, 12642),
(266, 12768),
(267, 12792),
(268, 12840),
(269, 12912),
(270, 13008),
(271, 13128),
(272, 13272),
(273, 13440),
(274, 13470),
(275, 13530),
(276, 13620),
(277, 13740),
(278, 13890),
(279, 14070),
(280, 14280),
(281, 14316),
(282, 14388),
(283, 14496),
(284, 14640),
(285, 14820),
(286, 15036),
(287, 15288),
(288, 15330),
(289, 15414),
(290, 15540),
(291, 15708),
(292, 15918),
(293, 16170),
(294, 16464),
(295, 16471),
(296, 16485),
(297, 16506),
(298, 16534),
(299, 16569),
(300, 16611),
(301, 16660),
(302, 16674),
(303, 16702),
(304, 16744),
(305, 16800),
(306, 16870),
(307, 16954),
(308, 17052),
(309, 17073),
(310, 17115),
(311, 17178),
(312, 17262),
(313, 17367),
(314, 17493),
(315, 17640),
(316, 17668),
(317, 17724),
(318, 17808),
(319, 17920),
(320, 18060),
(321, 18228),
(322, 18424),
(323, 18459),
(324, 18529),
(325, 18634),
(326, 18774),
(327, 18949),
(328, 19159),
(329, 19404),
(330, 19446),
(331, 19530),
(332, 19656),
(333, 19824),
(334, 20034),
(335, 20286),
(336, 20580),
(337, 20629),
(338, 20727),
(339, 20874),
(340, 21070),
(341, 21315),
(342, 21609),
(343, 21952),
(344, 21954),
(345, 21958),
(346, 21964),
(347, 21972),
(348, 21982),
(349, 21994),
(350, 22008),
(351, 22012),
(352, 22020),
(353, 22032),
(354, 22048),
(355, 22068),
(356, 22092),
(357, 22120),
(358, 22126),
(359, 22138),
(360, 22156),
(361, 22180),
(362, 22210),
(363, 22246),
(364, 22288),
(365, 22296),
(366, 22312),
(367, 22336),
(368, 22368),
(369, 22408),
(370, 22456),
(371, 22512),
(372, 22522),
(373, 22542),
(374, 22572),
(375, 22612),
(376, 22662),
(377, 22722),
(378, 22792),
(379, 22804),
(380, 22828),
(381, 22864),
(382, 22912),
(383, 22972),
(384, 23044),
(385, 23128),
(386, 23142),
(387, 23170),
(388, 23212),
(389, 23268),
(390, 23338),
(391, 23422),
(392, 23520),
(393, 23524),
(394, 23532),
(395, 23544),
(396, 23560),
(397, 23580),
(398, 23604),
(399, 23632),
(400, 23640),
(401, 23656),
(402, 23680),
(403, 23712),
(404, 23752),
(405, 23800),
(406, 23856),
(407, 23868),
(408, 23892),
(409, 23928),
(410, 23976),
(411, 24036),
(412, 24108),
(413, 24192),
(414, 24208),
(415, 24240),
(416, 24288),
(417, 24352),
(418, 24432),
(419, 24528),
(420, 24640),
(421, 24660),
(422, 24700),
(423, 24760),
(424, 24840),
(425, 24940),
(426, 25060),
(427, 25200),
(428, 25224),
(429, 25272),
(430, 25344),
(431, 25440),
(432, 25560),
(433, 25704),
(434, 25872),
(435, 25900),
(436, 25956),
(437, 26040),
(438, 26152),
(439, 26292),
(440, 26460),
(441, 26656),
(442, 26662),
(443, 26674),
(444, 26692),
(445, 26716),
(446, 26746),
(447, 26782),
(448, 26824),
(449, 26836),
(450, 26860),
(451, 26896),
(452, 26944),
(453, 27004),
(454, 27076),
(455, 27160),
(456, 27178),
(457, 27214),
(458, 27268),
(459, 27340),
(460, 27430),
(461, 27538),
(462, 27664),
(463, 27688),
(464, 27736),
(465, 27808),
(466, 27904),
(467, 28024),
(468, 28168),
(469, 28336),
(470, 28366),
(471, 28426),
(472, 28516),
(473, 28636),
(474, 28786),
(475, 28966),
(476, 29176),
(477, 29212),
(478, 29284),
(479, 29392),
(480, 29536),
(481, 29716),
(482, 29932),
(483, 30184),
(484, 30226),
(485, 30310),
(486, 30436),
(487, 30604),
(488, 30814),
(489, 31066),
(490, 31360),
(491, 31368),
(492, 31384),
(493, 31408),
(494, 31440),
(495, 31480),
(496, 31528),
(497, 31584),
(498, 31600),
(499, 31632),
(500, 31680),
(501, 31744),
(502, 31824),
(503, 31920),
(504, 32032),
(505, 32056),
(506, 32104),
(507, 32176),
(508, 32272),
(509, 32392),
(510, 32536),
(511, 32704),
(512, 32736),
(513, 32800),
(514, 32896),
(515, 33024),
(516, 33184),
(517, 33376),
(518, 33600),
(519, 33640),
(520, 33720),
(521, 33840),
(522, 34000),
(523, 34200),
(524, 34440),
(525, 34720),
(526, 34768),
(527, 34864),
(528, 35008),
(529, 35200),
(530, 35440),
(531, 35728),
(532, 36064),
(533, 36120),
(534, 36232),
(535, 36400),
(536, 36624),
(537, 36904),
(538, 37240),
(539, 37632),
(540, 37642),
(541, 37662),
(542, 37692),
(543, 37732),
(544, 37782),
(545, 37842),
(546, 37912),
(547, 37932),
(548, 37972),
(549, 38032),
(550, 38112),
(551, 38212),
(552, 38332),
(553, 38472),
(554, 38502),
(555, 38562),
(556, 38652),
(557, 38772),
(558, 38922),
(559, 39102),
(560, 39312),
(561, 39352),
(562, 39432),
(563, 39552),
(564, 39712),
(565, 39912),
(566, 40152),
(567, 40432),
(568, 40482),
(569, 40582),
(570, 40732),
(571, 40932),
(572, 41182),
(573, 41482),
(574, 41832),
(575, 41892),
(576, 42012),
(577, 42192),
(578, 42432),
(579, 42732),
(580, 43092),
(581, 43512),
(582, 43582),
(583, 43722),
(584, 43932),
(585, 44212),
(586, 44562),
(587, 44982),
(588, 45472),
(589, 45484),
(590, 45508),
(591, 45544),
(592, 45592),
(593, 45652),
(594, 45724),
(595, 45808),
(596, 45832),
(597, 45880),
(598, 45952),
(599, 46048),
(600, 46168),
(601, 46312),
(602, 46480),
(603, 46516),
(604, 46588),
(605, 46696),
(606, 46840),
(607, 47020),
(608, 47236),
(609, 47488),
(610, 47536),
(611, 47632),
(612, 47776),
(613, 47968),
(614, 48208),
(615, 48496),
(616, 48832),
(617, 48892),
(618, 49012),
(619, 49192),
(620, 49432),
(621, 49732),
(622, 50092),
(623, 50512),
(624, 50584),
(625, 50728),
(626, 50944),
(627, 51232),
(628, 51592),
(629, 52024),
(630, 52528),
(631, 52612),
(632, 52780),
(633, 53032),
(634, 53368),
(635, 53788),
(636, 54292),
(637, 54880),
(638, 54894),
(639, 54922),
(640, 54964),
(641, 55020),
(642, 55090),
(643, 55174),
(644, 55272),
(645, 55300),
(646, 55356),
(647, 55440),
(648, 55552),
(649, 55692),
(650, 55860),
(651, 56056),
(652, 56098),
(653, 56182),
(654, 56308),
(655, 56476),
(656, 56686),
(657, 56938),
(658, 57232),
(659, 57288),
(660, 57400),
(661, 57568),
(662, 57792),
(663, 58072),
(664, 58408),
(665, 58800),
(666, 58870),
(667, 59010),
(668, 59220),
(669, 59500),
(670, 59850),
(671, 60270),
(672, 60760),
(673, 60844),
(674, 61012),
(675, 61264),
(676, 61600),
(677, 62020),
(678, 62524),
(679, 63112),
(680, 63210),
(681, 63406),
(682, 63700),
(683, 64092),
(684, 64582),
(685, 65170),
(686, 65856),
(687, 65859),
(688, 65865),
(689, 65874),
(690, 65886),
(691, 65901),
(692, 65919),
(693, 65940),
(694, 65946),
(695, 65958),
(696, 65976),
(697, 66000),
(698, 66030),
(699, 66066),
(700, 66108),
(701, 66117),
(702, 66135),
(703, 66162),
(704, 66198),
(705, 66243),
(706, 66297),
(707, 66360),
(708, 66372),
(709, 66396),
(710, 66432),
(711, 66480),
(712, 66540),
(713, 66612),
(714, 66696),
(715, 66711),
(716, 66741),
(717, 66786),
(718, 66846),
(719, 66921),
(720, 67011),
(721, 67116),
(722, 67134),
(723, 67170),
(724, 67224),
(725, 67296),
(726, 67386),
(727, 67494),
(728, 67620),
(729, 67641),
(730, 67683),
(731, 67746),
(732, 67830),
(733, 67935),
(734, 68061),
(735, 68208),
(736, 68214),
(737, 68226),
(738, 68244),
(739, 68268),
(740, 68298),
(741, 68334),
(742, 68376),
(743, 68388),
(744, 68412),
(745, 68448),
(746, 68496),
(747, 68556),
(748, 68628),
(749, 68712),
(750, 68730),
(751, 68766),
(752, 68820),
(753, 68892),
(754, 68982),
(755, 69090),
(756, 69216),
(757, 69240),
(758, 69288),
(759, 69360),
(760, 69456),
(761, 69576),
(762, 69720),
(763, 69888),
(764, 69918),
(765, 69978),
(766, 70068),
(767, 70188),
(768, 70338),
(769, 70518),
(770, 70728),
(771, 70764),
(772, 70836),
(773, 70944),
(774, 71088),
(775, 71268),
(776, 71484),
(777, 71736),
(778, 71778),
(779, 71862),
(780, 71988),
(781, 72156),
(782, 72366),
(783, 72618),
(784, 72912),
(785, 72921),
(786, 72939),
(787, 72966),
(788, 73002),
(789, 73047),
(790, 73101),
(791, 73164),
(792, 73182),
(793, 73218),
(794, 73272),
(795, 73344),
(796, 73434),
(797, 73542),
(798, 73668),
(799, 73695),
(800, 73749),
(801, 73830),
(802, 73938),
(803, 74073),
(804, 74235),
(805, 74424),
(806, 74460),
(807, 74532),
(808, 74640),
(809, 74784),
(810, 74964),
(811, 75180),
(812, 75432),
(813, 75477),
(814, 75567),
(815, 75702),
(816, 75882),
(817, 76107),
(818, 76377),
(819, 76692),
(820, 76746),
(821, 76854),
(822, 77016),
(823, 77232),
(824, 77502),
(825, 77826),
(826, 78204),
(827, 78267),
(828, 78393),
(829, 78582),
(830, 78834),
(831, 79149),
(832, 79527),
(833, 79968),
(834, 79980),
(835, 80004),
(836, 80040),
(837, 80088),
(838, 80148),
(839, 80220),
(840, 80304),
(841, 80328),
(842, 80376),
(843, 80448),
(844, 80544),
(845, 80664),
(846, 80808),
(847, 80976),
(848, 81012),
(849, 81084),
(850, 81192),
(851, 81336),
(852, 81516),
(853, 81732),
(854, 81984),
(855, 82032),
(856, 82128),
(857, 82272),
(858, 82464),
(859, 82704),
(860, 82992),
(861, 83328),
(862, 83388),
(863, 83508),
(864, 83688),
(865, 83928),
(866, 84228),
(867, 84588),
(868, 85008),
(869, 85080),
(870, 85224),
(871, 85440),
(872, 85728),
(873, 86088),
(874, 86520),
(875, 87024),
(876, 87108),
(877, 87276),
(878, 87528),
(879, 87864),
(880, 88284),
(881, 88788),
(882, 89376),
(883, 89391),
(884, 89421),
(885, 89466),
(886, 89526),
(887, 89601),
(888, 89691),
(889, 89796),
(890, 89826),
(891, 89886),
(892, 89976),
(893, 90096),
(894, 90246),
(895, 90426),
(896, 90636),
(897, 90681),
(898, 90771),
(899, 90906),
(900, 91086),
(901, 91311),
(902, 91581),
(903, 91896),
(904, 91956),
(905, 92076),
(906, 92256),
(907, 92496),
(908, 92796),
(909, 93156),
(910, 93576),
(911, 93651),
(912, 93801),
(913, 94026),
(914, 94326),
(915, 94701),
(916, 95151),
(917, 95676),
(918, 95766),
(919, 95946),
(920, 96216),
(921, 96576),
(922, 97026),
(923, 97566),
(924, 98196),
(925, 98301),
(926, 98511),
(927, 98826),
(928, 99246),
(929, 99771),
(930, 100401),
(931, 101136),
(932, 101154),
(933, 101190),
(934, 101244),
(935, 101316),
(936, 101406),
(937, 101514),
(938, 101640),
(939, 101676),
(940, 101748),
(941, 101856),
(942, 102000),
(943, 102180),
(944, 102396),
(945, 102648),
(946, 102702),
(947, 102810),
(948, 102972),
(949, 103188),
(950, 103458),
(951, 103782),
(952, 104160),
(953, 104232),
(954, 104376),
(955, 104592),
(956, 104880),
(957, 105240),
(958, 105672),
(959, 106176),
(960, 106266),
(961, 106446),
(962, 106716),
(963, 107076),
(964, 107526),
(965, 108066),
(966, 108696),
(967, 108804),
(968, 109020),
(969, 109344),
(970, 109776),
(971, 110316),
(972, 110964),
(973, 111720),
(974, 111846),
(975, 112098),
(976, 112476),
(977, 112980),
(978, 113610),
(979, 114366),
(980, 115248),
(981, 115269),
(982, 115311),
(983, 115374),
(984, 115458),
(985, 115563),
(986, 115689),
(987, 115836),
(988, 115878),
(989, 115962),
(990, 116088),
(991, 116256),
(992, 116466),
(993, 116718),
(994, 117012),
(995, 117075),
(996, 117201),
(997, 117390),
(998, 117642),
(999, 117957),
(1000, 118335),
(10000, 6264360),
(100000, 346238256),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)