Oi pessoal,
Tem um jeito inteligente de determinar quantas vezes um dado número inteiro pode ser dividido por 2?
Por exemplo, 2 pode ser dividido 1 vez por 2.
Qualquer número ímpar não pode ser dividido nenhuma vez por 2.
Qualquer número n que for potência de 2 pode ser dividido por 2 exatamente lg n vezes (exemplo: 8 = 2³ então 8 pode ser dividido por 2 lg8 = 3 vezes).
Mas e para os outros números pares que não são potência de 2?
Ora, pense no número 12345678. Você sabe que ele é igual a 2 * 3^2 * 47 * 14593. Portanto, ele é divisível por 2 apenas 1 vez.
Outro exemplo: 765432200. Ele é 2^3 * 5^2 * 13 * 294397, portanto ele é divisível por 2, 3 vezes.
A forma mais rápida de determinar quantas vezes um número pode ser dividido por 2, e que é proporcional ao logaritmo de n, é realmente efetuar as divisões sucessivas por 2.
Se o número estiver em decimal, você pode contar quantos zeros à direita ele tem. Digamos o número (que já apresentei) 765432200. Como ele tem 2 zeros, ele é divisível por 10^2, ou seja, 2^2 * 5^2. Aí você já descontou 2 divisões. Depois disso, faça as divisões sucessivas de 7654322 por 2,
E se o número estiver em binário, basta contar os zeros à direita. Por exemplo, 765432200 em decimal é 101101100111111001000110001000 em binário, ou seja, tem 3 bits zero à direita, ou seja ,é divisível 3 vezes por 2.
O que eu tenho é o seguinte:
1 s←0
2 para i ← 1 até n faça
3 j←i
4 enquanto 2⌊j/2⌋ = j faça
5 j ← ⌊j/2⌋
6 s←s+1
7 devolva sOu seja, dado um número n, ele soma quantas vezes cada um dos números de 1 a n são divisíveis por 2.
Se n=5 por exemplo, então o resultado será: 0 + 1 + 0 + 2 + 0 = 3.
Se eu perguntar o valor de s ao final deste algoritmo, tem algum jeito de responder exatamente? Dizer que o algoritmo tem complexidade O (nlgn) não vale.
Você pode usar um algoritmo bem mais esperto que esse para determinar quantos números são divisíveis quantas vezes por 2. Acho que isso é um dos problemas do Projeto Euler, não?
Vou explicar mais ou menos como você tem de pensar.
Primeiramente, pegue os números de 1 a N:
1, 2, 3, 4, 5, … N
A seguir, marque cada número par uma vez:
1, 2_, 3, 4_, 5, 6_, … N -> isso vai dar N / 2 múltiplos de 2 uma vez.
A seguir, marque cada número múltiplo de 4 uma vez:
1, 2_, 3, 4__, 5, 6_, 7, 8__, 9, … N
Vá contando tudo, e veja que o que você vai ter é na verdade uma fórmula “fechada”.
[quote=entanglement][quote]
Ou seja, dado um número n, ele soma quantas vezes cada um dos números de 1 a n são divisíveis por 2.
[/quote]
Você pode usar um algoritmo bem mais esperto que esse para determinar quantos números são divisíveis quantas vezes por 2. Acho que isso é um dos problemas do Projeto Euler, não? [/quote]
Mais do que um algoritmo eficiente, eu preciso de uma fórmula matemática para determinar a soma que este algoritmo acima descreve.
Para tentar encontrar algum padrão, executei este algoritmo com n = 1024.
O resultado está abaixo, em pares ordenados, onde o primeiro numero é um inteiro, e o segundo é o número de vezes que este inteiro pode ser dividido por 2. Veja que eliminei os impares, ja que a imagem de um impar neste caso seria sempre zero.
Repare no padrão interessante que aparece:
(2,1)
(4,2)
(6,1)
(8,3)
(10,1)
(12,2)
(14,1)
(16,4)
(18,1)
(20,2)
(22,1)
(24,3)
(26,1)
(28,2)
(30,1)
(32,5)
(34,1)
(36,2)
(38,1)
(40,3)
(42,1)
(44,2)
(46,1)
(48,4)
(50,1)
(52,2)
(54,1)
(56,3)
(58,1)
(60,2)
(62,1)
(64,6)
(66,1)
(68,2)
(70,1)
(72,3)
(74,1)
(76,2)
(78,1)
(80,4)
(82,1)
(84,2)
(86,1)
(88,3)
(90,1)
(92,2)
(94,1)
(96,5)
(98,1)
(100,2)
(102,1)
(104,3)
(106,1)
(108,2)
(110,1)
(112,4)
(114,1)
(116,2)
(118,1)
(120,3)
(122,1)
(124,2)
(126,1)
(128,7)
(130,1)
(132,2)
(134,1)
(136,3)
(138,1)
(140,2)
(142,1)
(144,4)
(146,1)
(148,2)
(150,1)
(152,3)
(154,1)
(156,2)
(158,1)
(160,5)
(162,1)
(164,2)
(166,1)
(168,3)
(170,1)
(172,2)
(174,1)
(176,4)
(178,1)
(180,2)
(182,1)
(184,3)
(186,1)
(188,2)
(190,1)
(192,6)
(194,1)
(196,2)
(198,1)
(200,3)
(202,1)
(204,2)
(206,1)
(208,4)
(210,1)
(212,2)
(214,1)
(216,3)
(218,1)
(220,2)
(222,1)
(224,5)
(226,1)
(228,2)
(230,1)
(232,3)
(234,1)
(236,2)
(238,1)
(240,4)
(242,1)
(244,2)
(246,1)
(248,3)
(250,1)
(252,2)
(254,1)
(256,8)
(258,1)
(260,2)
(262,1)
(264,3)
(266,1)
(268,2)
(270,1)
(272,4)
(274,1)
(276,2)
(278,1)
(280,3)
(282,1)
(284,2)
(286,1)
(288,5)
(290,1)
(292,2)
(294,1)
(296,3)
(298,1)
(300,2)
(302,1)
(304,4)
(306,1)
(308,2)
(310,1)
(312,3)
(314,1)
(316,2)
(318,1)
(320,6)
(322,1)
(324,2)
(326,1)
(328,3)
(330,1)
(332,2)
(334,1)
(336,4)
(338,1)
(340,2)
(342,1)
(344,3)
(346,1)
(348,2)
(350,1)
(352,5)
(354,1)
(356,2)
(358,1)
(360,3)
(362,1)
(364,2)
(366,1)
(368,4)
(370,1)
(372,2)
(374,1)
(376,3)
(378,1)
(380,2)
(382,1)
(384,7)
(386,1)
(388,2)
(390,1)
(392,3)
(394,1)
(396,2)
(398,1)
(400,4)
(402,1)
(404,2)
(406,1)
(408,3)
(410,1)
(412,2)
(414,1)
(416,5)
(418,1)
(420,2)
(422,1)
(424,3)
(426,1)
(428,2)
(430,1)
(432,4)
(434,1)
(436,2)
(438,1)
(440,3)
(442,1)
(444,2)
(446,1)
(448,6)
(450,1)
(452,2)
(454,1)
(456,3)
(458,1)
(460,2)
(462,1)
(464,4)
(466,1)
(468,2)
(470,1)
(472,3)
(474,1)
(476,2)
(478,1)
(480,5)
(482,1)
(484,2)
(486,1)
(488,3)
(490,1)
(492,2)
(494,1)
(496,4)
(498,1)
(500,2)
(502,1)
(504,3)
(506,1)
(508,2)
(510,1)
(512,9)
(514,1)
(516,2)
(518,1)
(520,3)
(522,1)
(524,2)
(526,1)
(528,4)
(530,1)
(532,2)
(534,1)
(536,3)
(538,1)
(540,2)
(542,1)
(544,5)
(546,1)
(548,2)
(550,1)
(552,3)
(554,1)
(556,2)
(558,1)
(560,4)
(562,1)
(564,2)
(566,1)
(568,3)
(570,1)
(572,2)
(574,1)
(576,6)
(578,1)
(580,2)
(582,1)
(584,3)
(586,1)
(588,2)
(590,1)
(592,4)
(594,1)
(596,2)
(598,1)
(600,3)
(602,1)
(604,2)
(606,1)
(608,5)
(610,1)
(612,2)
(614,1)
(616,3)
(618,1)
(620,2)
(622,1)
(624,4)
(626,1)
(628,2)
(630,1)
(632,3)
(634,1)
(636,2)
(638,1)
(640,7)
(642,1)
(644,2)
(646,1)
(648,3)
(650,1)
(652,2)
(654,1)
(656,4)
(658,1)
(660,2)
(662,1)
(664,3)
(666,1)
(668,2)
(670,1)
(672,5)
(674,1)
(676,2)
(678,1)
(680,3)
(682,1)
(684,2)
(686,1)
(688,4)
(690,1)
(692,2)
(694,1)
(696,3)
(698,1)
(700,2)
(702,1)
(704,6)
(706,1)
(708,2)
(710,1)
(712,3)
(714,1)
(716,2)
(718,1)
(720,4)
(722,1)
(724,2)
(726,1)
(728,3)
(730,1)
(732,2)
(734,1)
(736,5)
(738,1)
(740,2)
(742,1)
(744,3)
(746,1)
(748,2)
(750,1)
(752,4)
(754,1)
(756,2)
(758,1)
(760,3)
(762,1)
(764,2)
(766,1)
(768,8)
(770,1)
(772,2)
(774,1)
(776,3)
(778,1)
(780,2)
(782,1)
(784,4)
(786,1)
(788,2)
(790,1)
(792,3)
(794,1)
(796,2)
(798,1)
(800,5)
(802,1)
(804,2)
(806,1)
(808,3)
(810,1)
(812,2)
(814,1)
(816,4)
(818,1)
(820,2)
(822,1)
(824,3)
(826,1)
(828,2)
(830,1)
(832,6)
(834,1)
(836,2)
(838,1)
(840,3)
(842,1)
(844,2)
(846,1)
(848,4)
(850,1)
(852,2)
(854,1)
(856,3)
(858,1)
(860,2)
(862,1)
(864,5)
(866,1)
(868,2)
(870,1)
(872,3)
(874,1)
(876,2)
(878,1)
(880,4)
(882,1)
(884,2)
(886,1)
(888,3)
(890,1)
(892,2)
(894,1)
(896,7)
(898,1)
(900,2)
(902,1)
(904,3)
(906,1)
(908,2)
(910,1)
(912,4)
(914,1)
(916,2)
(918,1)
(920,3)
(922,1)
(924,2)
(926,1)
(928,5)
(930,1)
(932,2)
(934,1)
(936,3)
(938,1)
(940,2)
(942,1)
(944,4)
(946,1)
(948,2)
(950,1)
(952,3)
(954,1)
(956,2)
(958,1)
(960,6)
(962,1)
(964,2)
(966,1)
(968,3)
(970,1)
(972,2)
(974,1)
(976,4)
(978,1)
(980,2)
(982,1)
(984,3)
(986,1)
(988,2)
(990,1)
(992,5)
(994,1)
(996,2)
(998,1)
(1000,3)
(1002,1)
(1004,2)
(1006,1)
(1008,4)
(1010,1)
(1012,2)
(1014,1)
(1016,3)
(1018,1)
(1020,2)
(1022,1)
(1024,10)
Tenho certeza que dá pra extrair um somatório daí. Só preciso de uma luz.
Ora, a fórmula é, conforme você viu,
|N/2| + |N/4| + |N/8| + … |N/M|
onde M é a maior potência de 2 menor ou igual a N.
[quote=entanglement]Vou explicar mais ou menos como você tem de pensar.
Primeiramente, pegue os números de 1 a N:
1, 2, 3, 4, 5, … N
A seguir, marque cada número par uma vez:
1, 2_, 3, 4_, 5, 6_, … N -> isso vai dar N / 2 múltiplos de 2 uma vez.
A seguir, marque cada número múltiplo de 4 uma vez:
1, 2_, 3, 4__, 5, 6_, 7, 8__, 9, … N
Vá contando tudo, e veja que o que você vai ter é na verdade uma fórmula “fechada”.
[/quote]
Não tinha visto essa resposta. Era isso mesmo que precisava.