Когда-то решал такую задачу. Есть программистский вариант решения. n >= 1 r = floor(log2(n)) + 1 - количество двоичных разрядов p = n-2^(r-1) - позиция числа в диапазоне [2^(r-1); 2^r) , p \in [0; 2^(r-1) ) f(n) = 1 + floor((p+1)/2) - sum( i=2 to r-1, floor(p/2^i) )
f(n)/(n(n+1)) это тоже самое что будто бы значение 1/(n(n+1)) посчиталось от каждого единичного бита числа n. тогда можно фиксировать бит k, и просто считать сумму по всем n таким что бит k есть в числе n получается мы посчитаем 1/(n(n+1)) от всех чисел в которых бит k есть и так сделаем для каждого бита бит k впервые встречается у числа 2^k, и после этого пропадает на числе 2*2^k, потом появляется у 3*2^k, пропадает в 4*2^k и так далее 1/(n(n+1)) = 1/n - 1/(n+1) тогда сумма таких значений для чисел между 2^k и 2*2^k будет равна 1/2^k - 1/2*2^k по итогу для фиксированного бита k сумма по n выходит вот такая: 1/2^k - 1/2*2^k + 1/3*2^k - 1/4*2^k .... = 1/2^k * (1/1 - 1/2 + 1/3 - 1/4 + 1/5 ...) = ln(2) / 2^k а сумма по всем возможным k будет равна ln(2) * 2 = ln(4)
Так можно решить в две строчки, если суммировать поразрядно. Скажем, для 3-го разряда имеем после сокращений 1/4 - 1/8 + 1/12 - 1/16 + ... = S/4, где S = 1 - 1/2 + 1/3 - 1/4 + ... = ln 2. А для k-го разряда сумма равна S / 2^(k-1). Суммирование по k очевидно даст 2S = ln4.
я также решал. Можно представить f(n) в виде бесконечной суммы с нулевым хвостом f(n) = sum f_k(n), где f_k(n) - kй бит числа n. Потом меняем местами знаки суммирования и получается то же самое
Как я не угадал с видео.... Включил, что б заснуть под какую-нибудь математику. А задачв оказалась настолько интересной, что наоборот расшевелила мозг.
Спасибо! Видео смотрел как фильм с непредсказуемой концовкой. На одном дыхании) Ожидал что ответ будет -1/12 или 3,1415.. , но ln4 тоже неплохо. Когда решаю сложные задачи по программированию, тоже часто приходится искать паттерны, цикличности, преобразования. И я искренне понимаю какой кайф, когда наконец нашел решение и ускорил функцию во много раз.
Мне ролик понравился. Я пытаюсь поставить и решить подобную задачу. Разрядность двоичного числа связана с выборками. А это горизонтали треугольника Паскаля. Эту часть задачи я решил. В моей задаче просматриваются ряды. Так что ролик уважаемого автора я использую в качестве импульса для решения своей задачи. Я не математик, я фермист. Это даёт возможность без угрозы для репутации высказать предположение: Ноль может быть мнимым. Мне кажется я это доказал. Конечный вывод звучит так: Единица в степени "мнимый ноль" равна вещественной оси! А гипотеза звучит так: на пересечении вещественной и мнимой осей существует два нуля: "действительный ноль" и "мнимый ноль". Эта гипотеза всплыла при решении моей задачи.
Количество единиц для первых 7 чисел равно 12, для первых 15 чисел равно 32, для первых 31 чисел равно 80, а в общем для первых (2в n степени -1)чисел равно n÷2×(2 в n степени), например 5÷2×32=80, 4÷2×16=32, 3÷2×8=12, 2÷2×4=4, 1÷2×2=1.
перестал в себя верить, как в будущего математика-физика-инженера. появляются мысли, что это не моё. но вот твои видео ещё вселяют надежду, что это все не зря. а задача реально классная.
Как-то грустно было доказано что f(2n)=f(n), а f(2n+1)=f(n)+1. На самом деле там все просто. Умножение на два в двоичной системе - это дописать к концу числа 0. Очевидно что такое действие не меняет количество единиц в числе. А 2n+1 - это дописать к концу числа единицу. И очевидно, что такое действие увеличивает число единиц на одну. То есть заметить паттерн - отличный момент для начала, но затем это можно просто свести к двум операциям - приписывание нуля и приписывание единицы.
Ну в целом бинарные ствига так работают, что удвоенное числа не меняет количество единиц в его двоичной записи. Потом дойти до того, что колво единиц у нечетного числа на 1 больше чем четного оже можно. Но как сходу это заменить - это я не знаю. Зато когда с дивана смотришь все понятно и такой, ну да, тут все верно))
Сразу приходит в голову сменить порядок суммирования. Сначала сумма по всем числам с одной единицей, затем с двумя и т.д. Не считал, но должно несложно получиться.
Был у меня как-то ряд n от 2 до бесконечности 1/(ln^2(2)+ln^2(3)+…ln^2(n)) так я его чет взять и не смог P. S. Для поднимания, при n=2 будет 1/ln^2(2) При n=3 будет 1/ln^2(2)+1/(ln^2(2)+ln^2(3))
Ну как бы i-ый разряд числа n в двоичном виде = floor(n / 2^i) mod 2 (считая с нуля справа налево), соответственно количество единиц - это сумма по i от 0 до 2 ^ floor(log2(n))
Кажется что для программиста увидеть что f(2n) = f(n) не составит труда, ведь это просто смещение влево на 1 разряд. То что f(2n+1) = f(2n) + 1 тоже, ведь мы просто в последнем бите заменяем 0 на 1.
Просто автор нашел альтернативное, красивое и не очевидное решение, но при этом не нашел прямолинейное решение через поразрядную сумму, которым я думаю все и решали
Решил минут за 20 в уме. Из них 3 минуты ушло, чтобы сообразить, что ответ равен: (1 + 1/2 + 1/4 + 1/8 + ...)×(1 - 1/2 + 1/3 - 1/4 + 1/5 - ...), а остальное время скрипел мозгами, вспоминая, что второй множитель равен ln2 и как это вывести... Причём минут 15 думал, что второй ряд равен arctg1=π/4, и пытался это доказать 🤦♂️ Если в ШАД никто не решил, то это позор.
*решение o1-preview:* Чтобы найти сумму ряда S = ∑(n=1 до ∞) f(n) / (n * (n+1)), где f(n) - это количество единиц в двоичном представлении числа n, используем преобразование: 1 / (n * (n+1)) = 1/n - 1/(n+1) Теперь сумма превращается в: S = ∑(n=1 до ∞) f(n) * (1/n - 1/(n+1)) Разложим сумму: S = ∑(n=1 до ∞) f(n)/n - ∑(n=1 до ∞) f(n)/(n+1) Во втором сомножителе меняем индекс (k = n + 1): S = ∑(n=1 до ∞) f(n)/n - ∑(k=2 до ∞) f(k-1)/k Теперь можно записать: S = f(1)/1 + ∑(n=2 до ∞) (f(n) - f(n-1))/n Исследуем разность f(n) - f(n-1). При увеличении n на 1 количество единиц в двоичном представлении меняется на +1, 0 или отрицательное число. Далее заметим, что сумма положительных членов сходится к (\ln(2)), поскольку она связана с рядом обратных нечётных чисел, а отрицательные члены компенсируют излишки. В результате можно показать, что общая сумма сходится к (ln(4)). *Ответ: ln 4* В общем я понял, что все эти олимпиадные задачи для нейросетей ерунда, надо что-то принципиально более сложное.
@@Profimatika_vyshmat Тогда вот решение o1-mini, обычно он выдаёт более качественный ответ: Чтобы найти сумму ряда S = ∑(n=1 до ∞) f(n)/(n*(n+1)), где f(n) - это количество единиц в двоичном представлении числа n, воспользуемся следующими шагами. *Шаг 1: Разложение* 1/(n*(n+1)) Заметим, что: 1/(n*(n+1)) = 1/n - 1/(n+1) Тогда сумма S может быть переписана как: S = ∑(n=1 до ∞) f(n)/n - ∑(n=1 до ∞) f(n)/(n+1) Сдвинем индекс во второй сумме: S = f(1) + ∑(n=2 до ∞) (f(n)/n - f(n-1)/n) = 1 + ∑(n=2 до ∞) (f(n) - f(n-1))/n *Шаг 2: Свойства f(n) - f(n-1)* Разница f(n) - f(n-1) связана с количеством незначащих единиц в двоичном представлении числа n-1. Если n-1 оканчивается на t единиц, то: f(n) - f(n-1) = 1 - t *Шаг 3: Перестановка сумм* Используем представление f(n) как суммы битов: f(n) = ∑(k=0 до ∞) b_k(n), где b_k(n) - это k-ый бит числа n. Таким образом, сумма S может быть представлена как: S = ∑(k=0 до ∞) ∑(n: b_k(n)=1) (1/n - 1/(n+1)) *Шаг 4: Вычисление внутренней суммы* Для каждого бита k множество чисел n, у которых b_k(n) = 1, повторяется с периодом 2^(k+1). Внутренняя сумма для фиксированного k выглядит как: S_k = ∑(m=0 до ∞) (1/(m*2^(k+1) + 2^k) - 1/((m+1)*2^(k+1))) Эта сумма стремится к: S_k = ln(2)/2^k *Шаг 5: Суммирование по всем битам* Итоговая сумма S равна: S = ∑(k=0 до ∞) S_k = ∑(k=0 до ∞) ln(2)/2^k = 2*ln(2) *Проверка:* Частичные суммы S_8 ≈ 1.38175, а 2*ln(2) ≈ 1.38629, что подтверждает правильность расчета. *Ответ:* Сумма ряда равна 2*ln(2).
Закреплю коммент того человека, кто найдет явное выражение для f(n), дерзайте)
Закрепи еще и тот, в котором будет описана практическая польза от этого ряда ;)
Это ведь как-то связано с анализом данных, да?
Выражение в элементарных функциях и арифметических операциях? )
Иди в пень
Когда-то решал такую задачу.
Есть программистский вариант решения.
n >= 1
r = floor(log2(n)) + 1 - количество двоичных разрядов
p = n-2^(r-1) - позиция числа в диапазоне [2^(r-1); 2^r) , p \in [0; 2^(r-1) )
f(n) = 1 + floor((p+1)/2) - sum( i=2 to r-1, floor(p/2^i) )
en.wikipedia.org/wiki/Hamming_weight
f(n)/(n(n+1)) это тоже самое что будто бы значение 1/(n(n+1)) посчиталось от каждого единичного бита числа n.
тогда можно фиксировать бит k, и просто считать сумму по всем n таким что бит k есть в числе n
получается мы посчитаем 1/(n(n+1)) от всех чисел в которых бит k есть и так сделаем для каждого бита
бит k впервые встречается у числа 2^k, и после этого пропадает на числе 2*2^k, потом появляется у 3*2^k, пропадает в 4*2^k и так далее
1/(n(n+1)) = 1/n - 1/(n+1) тогда сумма таких значений для чисел между 2^k и 2*2^k будет равна 1/2^k - 1/2*2^k
по итогу для фиксированного бита k сумма по n выходит вот такая:
1/2^k - 1/2*2^k + 1/3*2^k - 1/4*2^k .... = 1/2^k * (1/1 - 1/2 + 1/3 - 1/4 + 1/5 ...) = ln(2) / 2^k
а сумма по всем возможным k будет равна ln(2) * 2 = ln(4)
охренеть..
салам ты из ну, просто имя очень знакомое? какой грейд у тебя по Калкулусу?
Креативно, респект
Ролики на этом канале это единственная причина, почему я не покидаю ютуб
зови автора на рутуб)
Как ни странно, но смотрится на одном дыхании. Очень красивая задача с красивым ответом. Спасибо автору.
Так можно решить в две строчки, если суммировать поразрядно. Скажем, для 3-го разряда имеем после сокращений 1/4 - 1/8 + 1/12 - 1/16 + ... = S/4, где S = 1 - 1/2 + 1/3 - 1/4 + ... = ln 2.
А для k-го разряда сумма равна S / 2^(k-1). Суммирование по k очевидно даст 2S = ln4.
я также решал. Можно представить f(n) в виде бесконечной суммы с нулевым хвостом f(n) = sum f_k(n), где f_k(n) - kй бит числа n. Потом меняем местами знаки суммирования и получается то же самое
По чаще такие задачи, интересно смотреть
Очень классное решение! Обожаю ваш канал, лучшие❤
Как я не угадал с видео.... Включил, что б заснуть под какую-нибудь математику. А задачв оказалась настолько интересной, что наоборот расшевелила мозг.
Спасибо!
Видео смотрел как фильм с непредсказуемой концовкой. На одном дыхании)
Ожидал что ответ будет -1/12 или 3,1415.. , но ln4 тоже неплохо.
Когда решаю сложные задачи по программированию, тоже часто приходится искать паттерны, цикличности, преобразования. И я искренне понимаю какой кайф, когда наконец нашел решение и ускорил функцию во много раз.
12:35 потому что при умножении на 2 происходит побитовый сдвиг на 1 разряд влево, вот и количество не меняется
Мне ролик понравился.
Я пытаюсь поставить и решить подобную задачу.
Разрядность двоичного числа связана с выборками.
А это горизонтали треугольника Паскаля.
Эту часть задачи я решил.
В моей задаче просматриваются ряды.
Так что ролик уважаемого автора я использую в качестве импульса для решения своей задачи.
Я не математик, я фермист.
Это даёт возможность без угрозы для репутации высказать предположение:
Ноль может быть мнимым.
Мне кажется я это доказал.
Конечный вывод звучит так:
Единица в степени "мнимый ноль" равна вещественной оси!
А гипотеза звучит так: на пересечении вещественной и мнимой осей существует два нуля: "действительный ноль" и "мнимый ноль".
Эта гипотеза всплыла при решении моей задачи.
Это божественно лучшее, что я видел в своей жизни
Красиво. Спасибо за видео!
Спасибо, как раз не понимал тему перевода из двоичной в шестнадцатеричную систему счисления
В целом было очень интересно. Для меня сложным показалось "угадать" ряд Тейлора для логарифма, я их все забыл за прошедшие 32 года.
отлично, действительно красивое решение, не знаю как в яндексе предполагали, чтобы это решали, видимо к шаду нужно готовиться как к олимпиаде...
без ежа ничего не понял
Количество единиц для первых 7 чисел равно 12, для первых 15 чисел равно 32, для первых 31 чисел равно 80, а в общем для первых (2в n степени -1)чисел равно n÷2×(2 в n степени), например 5÷2×32=80, 4÷2×16=32, 3÷2×8=12, 2÷2×4=4, 1÷2×2=1.
Классная задача, тож оч понравилась, видос кайф
Легчайше, решил без видео) Там еще когда был удвоенный ряд +1, единицу можно было в него запихать, сделав суммирование от n=0
перестал в себя верить, как в будущего математика-физика-инженера. появляются мысли, что это не моё. но вот твои видео ещё вселяют надежду, что это все не зря.
а задача реально классная.
Классная задача. Спасибо!
какая красота
Крутой канал, вспомнил универ !)
@@Rome.Legion Спасибо!)
Как-то грустно было доказано что f(2n)=f(n), а f(2n+1)=f(n)+1. На самом деле там все просто. Умножение на два в двоичной системе - это дописать к концу числа 0. Очевидно что такое действие не меняет количество единиц в числе. А 2n+1 - это дописать к концу числа единицу. И очевидно, что такое действие увеличивает число единиц на одну. То есть заметить паттерн - отличный момент для начала, но затем это можно просто свести к двум операциям - приписывание нуля и приписывание единицы.
Ну в целом бинарные ствига так работают, что удвоенное числа не меняет количество единиц в его двоичной записи. Потом дойти до того, что колво единиц у нечетного числа на 1 больше чем четного оже можно. Но как сходу это заменить - это я не знаю. Зато когда с дивана смотришь все понятно и такой, ну да, тут все верно))
Сразу приходит в голову сменить порядок суммирования. Сначала сумма по всем числам с одной единицей, затем с двумя и т.д. Не считал, но должно несложно получиться.
По крайней мере для чисел вида 2^n, f(n) вернёт 1, а там остаётся лишь проанализировать числа иных видов ¯\_(ツ)_/¯
1:18 Все чиселки переберем. Оптимистично...
Был у меня как-то ряд n от 2 до бесконечности 1/(ln^2(2)+ln^2(3)+…ln^2(n)) так я его чет взять и не смог
P. S. Для поднимания, при n=2 будет 1/ln^2(2)
При n=3 будет 1/ln^2(2)+1/(ln^2(2)+ln^2(3))
Число едениц стремится к половине от логарифма по основанию 2
f(n) -- это функция Хэмминга(Hamming weight(x)). Её нельзя представить в явном виде, а только через рекурсию.
Ну как бы i-ый разряд числа n в двоичном виде = floor(n / 2^i) mod 2 (считая с нуля справа налево), соответственно количество единиц - это сумма по i от 0 до 2 ^ floor(log2(n))
@@petuhatopovich7372 под явным видом представления подразумевается использование только элементарных функций
@@petuhatopovich7372 Да, похоже, ты прав, но сомневаюсь, что это бы помогло решить задачу таким способом (по крайней мере это будет сложнее).😅
Количество едениц не превышает логарифма по основанию 2, потому ряд сходится. Программу надо написать и посчитать
Очень красивая задача) Но и правда сложно
Симпатично!
Побуду немного душным. Когда доказывал сходимость, забыл сказать, что ряд ограничен снизу. Ведь в ином случае он мог бы уходить в минус бесконечность
Кажется что для программиста увидеть что f(2n) = f(n) не составит труда, ведь это просто смещение влево на 1 разряд.
То что f(2n+1) = f(2n) + 1 тоже, ведь мы просто в последнем бите заменяем 0 на 1.
Совы нет, вот поэтому ты мучился так долго😊
Можете поделится опытом использования платного вольфрама? Думаю покупать или нет, а в интернете нормального обзора нет(
@@ВадимБекетов-г4к я более чем доволен)
Step by step solution часто выручает, чтобы быстро решить какой-то диффур или интеграл)
@@Profimatika_vyshmat благодарю!!!
Ещё можно заметить, что эта функция сохраняет операцию сложения
f(1 + 1) ≠ f(1) + f(1)
@@outerrrr а, да. Тогда можно сказать, что она сохраняет сумму только для сумм из степеней двойки, кроме степени 0.
Так логорифм по основанию 2 это логорифм деленый на логорифм 2. Вот логорифм 2 и выполз
Красивая задача и красивоет решение!
Высыпайтесь )
Спасибо)
А подскажи пожалуйста, в какой программе ты пишешь?
Это Goodnotes. Приложение для iPad, но вроде щас и на Samsung можно. Хорошее приложение. На Android аналог хороший - touchnotes
Решил минут за 20, не верю, что в ШАДе никто не решил. Задача же вообще читается по структуре
Просто автор нашел альтернативное, красивое и не очевидное решение, но при этом не нашел прямолинейное решение через поразрядную сумму, которым я думаю все и решали
@@no_name128что за поразрядная сумма?
Зашёл посмотреть на математику, а вижу как причёсывают сумму😅
Браво
Решил минут за 20 в уме. Из них 3 минуты ушло, чтобы сообразить, что ответ равен:
(1 + 1/2 + 1/4 + 1/8 + ...)×(1 - 1/2 + 1/3 - 1/4 + 1/5 - ...),
а остальное время скрипел мозгами, вспоминая, что второй множитель равен ln2 и как это вывести...
Причём минут 15 думал, что второй ряд равен arctg1=π/4, и пытался это доказать 🤦♂️
Если в ШАД никто не решил, то это позор.
Юморист
*решение o1-preview:*
Чтобы найти сумму ряда S = ∑(n=1 до ∞) f(n) / (n * (n+1)), где f(n) - это количество единиц в двоичном представлении числа n, используем преобразование:
1 / (n * (n+1)) = 1/n - 1/(n+1)
Теперь сумма превращается в:
S = ∑(n=1 до ∞) f(n) * (1/n - 1/(n+1))
Разложим сумму:
S = ∑(n=1 до ∞) f(n)/n - ∑(n=1 до ∞) f(n)/(n+1)
Во втором сомножителе меняем индекс (k = n + 1):
S = ∑(n=1 до ∞) f(n)/n - ∑(k=2 до ∞) f(k-1)/k
Теперь можно записать:
S = f(1)/1 + ∑(n=2 до ∞) (f(n) - f(n-1))/n
Исследуем разность f(n) - f(n-1). При увеличении n на 1 количество единиц в двоичном представлении меняется на +1, 0 или отрицательное число.
Далее заметим, что сумма положительных членов сходится к (\ln(2)), поскольку она связана с рядом обратных нечётных чисел, а отрицательные члены компенсируют излишки. В результате можно показать, что общая сумма сходится к (ln(4)).
*Ответ: ln 4*
В общем я понял, что все эти олимпиадные задачи для нейросетей ерунда, надо что-то принципиально более сложное.
@@andreiantonov7303 на моменте разложения суммы неверно, так как это оба расходящихся ряда)
@@Profimatika_vyshmat Тогда вот решение o1-mini, обычно он выдаёт более качественный ответ:
Чтобы найти сумму ряда S = ∑(n=1 до ∞) f(n)/(n*(n+1)), где f(n) - это количество единиц в двоичном представлении числа n, воспользуемся следующими шагами.
*Шаг 1: Разложение* 1/(n*(n+1)) Заметим, что: 1/(n*(n+1)) = 1/n - 1/(n+1) Тогда сумма S может быть переписана как: S = ∑(n=1 до ∞) f(n)/n - ∑(n=1 до ∞) f(n)/(n+1) Сдвинем индекс во второй сумме: S = f(1) + ∑(n=2 до ∞) (f(n)/n - f(n-1)/n) = 1 + ∑(n=2 до ∞) (f(n) - f(n-1))/n
*Шаг 2: Свойства f(n) - f(n-1)* Разница f(n) - f(n-1) связана с количеством незначащих единиц в двоичном представлении числа n-1. Если n-1 оканчивается на t единиц, то: f(n) - f(n-1) = 1 - t
*Шаг 3: Перестановка сумм* Используем представление f(n) как суммы битов: f(n) = ∑(k=0 до ∞) b_k(n), где b_k(n) - это k-ый бит числа n.
Таким образом, сумма S может быть представлена как: S = ∑(k=0 до ∞) ∑(n: b_k(n)=1) (1/n - 1/(n+1))
*Шаг 4: Вычисление внутренней суммы* Для каждого бита k множество чисел n, у которых b_k(n) = 1, повторяется с периодом 2^(k+1). Внутренняя сумма для фиксированного k выглядит как: S_k = ∑(m=0 до ∞) (1/(m*2^(k+1) + 2^k) - 1/((m+1)*2^(k+1))) Эта сумма стремится к: S_k = ln(2)/2^k
*Шаг 5: Суммирование по всем битам* Итоговая сумма S равна: S = ∑(k=0 до ∞) S_k = ∑(k=0 до ∞) ln(2)/2^k = 2*ln(2)
*Проверка:* Частичные суммы S_8 ≈ 1.38175, а 2*ln(2) ≈ 1.38629, что подтверждает правильность расчета.
*Ответ:* Сумма ряда равна 2*ln(2).
@@Profimatika_vyshmat если пропустить это действие, то будет верное преобразование в сумму f(n)-f(n-1)/n
Знающие люди, подскажите, пожалуйста, каким приложением для записей пользуется автор?
@@protasoff4712 GoodNotes)
С функцией Хэмминга всё понятно, но Ёж-то где? 😅
Ёж наверно заснул и свалился под стол. Либо сложность задачи перегрела ему мозг и он свалися под стол. Короче, ёж под столом.
5:45😂
круто
Не спойлер, а инсайд ;)
Единственная обратная связь, которую я могу тут дать: даже еж спать ушёл, автор, высыпайся!
С ежом бы максимум до 2 ночи задержался.
Без ежа ничего не понятно.
Что за программа?
GoodNotes
У тебя ряд не сходится абсолютно, при этом в ходе решения ты переставлял его члены. Решение не верное)
Изначальный ряд сходится абсолютно, я это показал в процессе решения)