ОЛИМПИАДНЫЙ РЯД, КОТОРЫЙ НИКТО НЕ РЕШИЛ! | ШАД ЯНДЕКС

[@Profimatika_vyshmat]

Закреплю коммент того человека, кто найдет явное выражение для f(n), дерзайте)

[@101picofarad]

Закрепи еще и тот, в котором будет описана практическая польза от этого ряда ;) Это ведь как-то связано с анализом данных, да?

[@maxm33]

Выражение в элементарных функциях и арифметических операциях? )

[@Бываеттак-ь7л]

Иди в пень

[@МихаилФирсов-з1л]

Когда-то решал такую задачу. Есть программистский вариант решения. 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) )

[@usikpa]

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)

[@elgracho]

охренеть..

[@TheDanchoSuper]

салам ты из ну, просто имя очень знакомое? какой грейд у тебя по Калкулусу?

[@ПавелБережной-ц3г]

Креативно, респект

[@stark8593]

Ролики на этом канале это единственная причина, почему я не покидаю ютуб

[@TheBishop_2051]

зови автора на рутуб)

[@5735zzzlo]

Как ни странно, но смотрится на одном дыхании. Очень красивая задача с красивым ответом. Спасибо автору.

[@Павел-в2щ]

Так можно решить в две строчки, если суммировать поразрядно. Скажем, для 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.

[@stas4017]

я также решал. Можно представить f(n) в виде бесконечной суммы с нулевым хвостом f(n) = sum f_k(n), где f_k(n) - kй бит числа n. Потом меняем местами знаки суммирования и получается то же самое

[@РомаСоловьёв-с1у]

По чаще такие задачи, интересно смотреть

[@АртемВирский]

Как я не угадал с видео.... Включил, что б заснуть под какую-нибудь математику. А задачв оказалась настолько интересной, что наоборот расшевелила мозг.

[@MicheRR]

перестал в себя верить, как в будущего математика-физика-инженера. появляются мысли, что это не моё. но вот твои видео ещё вселяют надежду, что это все не зря. а задача реально классная.

[@fedkaminskiy]

Очень классное решение! Обожаю ваш канал, лучшие❤

[@МихаилКолеватов-у6д]

12:35 потому что при умножении на 2 происходит побитовый сдвиг на 1 разряд влево, вот и количество не меняется

[@zerochannel6686]

Это божественно лучшее, что я видел в своей жизни

[@TUZZ5000]

Спасибо! Видео смотрел как фильм с непредсказуемой концовкой. На одном дыхании) Ожидал что ответ будет -1/12 или 3,1415.. , но ln4 тоже неплохо. Когда решаю сложные задачи по программированию, тоже часто приходится искать паттерны, цикличности, преобразования. И я искренне понимаю какой кайф, когда наконец нашел решение и ускорил функцию во много раз.

[@gopstr]

Красиво. Спасибо за видео!

[@vovatereshkin3080]

Мне ролик понравился. Я пытаюсь поставить и решить подобную задачу. Разрядность двоичного числа связана с выборками. А это горизонтали треугольника Паскаля. Эту часть задачи я решил. В моей задаче просматриваются ряды. Так что ролик уважаемого автора я использую в качестве импульса для решения своей задачи. Я не математик, я фермист. Это даёт возможность без угрозы для репутации высказать предположение: Ноль может быть мнимым. Мне кажется я это доказал. Конечный вывод звучит так: Единица в степени "мнимый ноль" равна вещественной оси! А гипотеза звучит так: на пересечении вещественной и мнимой осей существует два нуля: "действительный ноль" и "мнимый ноль". Эта гипотеза всплыла при решении моей задачи.

[@MathPTU]

отлично, действительно красивое решение, не знаю как в яндексе предполагали, чтобы это решали, видимо к шаду нужно готовиться как к олимпиаде...

[@stanislavbutsky8432]

В целом было очень интересно. Для меня сложным показалось "угадать" ряд Тейлора для логарифма, я их все забыл за прошедшие 32 года.

[@المجدللشعبالسوري]

Спасибо, как раз не понимал тему перевода из двоичной в шестнадцатеричную систему счисления

[@НикитаВасильев-в7и]

какая красота

[@alexandermorozov2248]

Хорошо бы проверить ответ численно; посчитать частичную сумму данного ряда на компьютере и посмотреть, будет ли частичная суммая ряда сходиться к ln(4) при больших n или нет ;)

[@dobrekzz]

Классная задача, тож оч понравилась, видос кайф

[@ЕвгенийАристов-и5г]

Количество единиц для первых 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.

[@Math_is_my_lady]

Классная задача. Спасибо!

[@КириллКрыжановский-к9з]

Ну в целом бинарные ствига так работают, что удвоенное числа не меняет количество единиц в его двоичной записи. Потом дойти до того, что колво единиц у нечетного числа на 1 больше чем четного оже можно. Но как сходу это заменить - это я не знаю. Зато когда с дивана смотришь все понятно и такой, ну да, тут все верно))

[@Rome.Legion]

Крутой канал, вспомнил универ !)

[@Profimatika_vyshmat]

@@Rome.Legion Спасибо!)

[@dog-foxfo2887]

без ежа ничего не понял

[@Pizhdak]

Легчайше, решил без видео) Там еще когда был удвоенный ряд +1, единицу можно было в него запихать, сделав суммирование от n=0

[@operator3577]

По крайней мере для чисел вида 2^n, f(n) вернёт 1, а там остаётся лишь проанализировать числа иных видов ¯\_(ツ)_/¯

[@michaelbuzuverov67]

Как-то грустно было доказано что f(2n)=f(n), а f(2n+1)=f(n)+1. На самом деле там все просто. Умножение на два в двоичной системе - это дописать к концу числа 0. Очевидно что такое действие не меняет количество единиц в числе. А 2n+1 - это дописать к концу числа единицу. И очевидно, что такое действие увеличивает число единиц на одну. То есть заметить паттерн - отличный момент для начала, но затем это можно просто свести к двум операциям - приписывание нуля и приписывание единицы.

[@СтаниславСерегин-р4ч]

Сразу приходит в голову сменить порядок суммирования. Сначала сумма по всем числам с одной единицей, затем с двумя и т.д. Не считал, но должно несложно получиться.

[@SunakSunak-b9t]

Количество едениц не превышает логарифма по основанию 2, потому ряд сходится. Программу надо написать и посчитать

[@sto_k1357]

1:18 Все чиселки переберем. Оптимистично...

[@ЛевВладимиров-й7з]

Решил минут за 20, не верю, что в ШАДе никто не решил. Задача же вообще читается по структуре

[@no_name128]

Просто автор нашел альтернативное, красивое и не очевидное решение, но при этом не нашел прямолинейное решение через поразрядную сумму, которым я думаю все и решали

[@СтаниславВокеутов-ю2э]

​@@no_name128что за поразрядная сумма?

[@MrHellko]

Кажется что для программиста увидеть что f(2n) = f(n) не составит труда, ведь это просто смещение влево на 1 разряд. То что f(2n+1) = f(2n) + 1 тоже, ведь мы просто в последнем бите заменяем 0 на 1.

[@РоманРузанкин-у1д]

Ещё можно заметить, что эта функция сохраняет операцию сложения

[@outerrrr]

f(1 + 1) ≠ f(1) + f(1)

[@РоманРузанкин-у1д]

@@outerrrr а, да. Тогда можно сказать, что она сохраняет сумму только для сумм из степеней двойки, кроме степени 0.

[@MishinSA]

Симпатично!

[@Homomorph]

f(n) -- это функция Хэмминга(Hamming weight(x)). Её нельзя представить в явном виде, а только через рекурсию.

[@petuhatopovich7372]

Ну как бы i-ый разряд числа n в двоичном виде = floor(n / 2^i) mod 2 (считая с нуля справа налево), соответственно количество единиц - это сумма по i от 0 до 2 ^ floor(log2(n))

[@ЮраНазаров-э9с]

​@@petuhatopovich7372 под явным видом представления подразумевается использование только элементарных функций

[@Homomorph]

​​@@petuhatopovich7372 Да, похоже, ты прав, но сомневаюсь, что это бы помогло решить задачу таким способом (по крайней мере это будет сложнее).😅

[@ВадимБекетов-г4к]

Можете поделится опытом использования платного вольфрама? Думаю покупать или нет, а в интернете нормального обзора нет(

[@Profimatika_vyshmat]

@@ВадимБекетов-г4к я более чем доволен) Step by step solution часто выручает, чтобы быстро решить какой-то диффур или интеграл)

[@ВадимБекетов-г4к]

@@Profimatika_vyshmat благодарю!!!

[@OlegLomakin756]

Был у меня как-то ряд 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))

[@xMORAENNx]

Побуду немного душным. Когда доказывал сходимость, забыл сказать, что ряд ограничен снизу. Ведь в ином случае он мог бы уходить в минус бесконечность

[@Mr.Not_Sure]

Решил минут за 20 в уме. Из них 3 минуты ушло, чтобы сообразить, что ответ равен: (1 + 1/2 + 1/4 + 1/8 + ...)×(1 - 1/2 + 1/3 - 1/4 + 1/5 - ...), а остальное время скрипел мозгами, вспоминая, что второй множитель равен ln2 и как это вывести... Причём минут 15 думал, что второй ряд равен arctg1=π/4, и пытался это доказать 🤦‍♂️ Если в ШАД никто не решил, то это позор.

[@СтаниславВокеутов-ю2э]

Юморист

[@begula_chan]

Очень красивая задача) Но и правда сложно

[@SunakSunak-b9t]

Число едениц стремится к половине от логарифма по основанию 2

[@protasoff4712]

Знающие люди, подскажите, пожалуйста, каким приложением для записей пользуется автор?

[@Profimatika_vyshmat]

@@protasoff4712 GoodNotes)

[@OlegLomakin756]

Браво

[@laletonio]

А подскажи пожалуйста, в какой программе ты пишешь?

[@ryakhovskiyy]

Это Goodnotes. Приложение для iPad, но вроде щас и на Samsung можно. Хорошее приложение. На Android аналог хороший - touchnotes

[@sagdtadjimuratov129]

Совы нет, вот поэтому ты мучился так долго😊

[@silendil]

Так логорифм по основанию 2 это логорифм деленый на логорифм 2. Вот логорифм 2 и выполз

[@ALPHA-zq5gv]

круто

[@Tyvzar]

Красивая задача и красивоет решение! Высыпайтесь )

[@Profimatika_vyshmat]

Спасибо)

[@Homomorph]

Зашёл посмотреть на математику, а вижу как причёсывают сумму😅

[@Anti_During]

Не спойлер, а инсайд ;)

[@elisorium]

С функцией Хэмминга всё понятно, но Ёж-то где? 😅

[@DB-zz8zm]

Ёж наверно заснул и свалился под стол. Либо сложность задачи перегрела ему мозг и он свалися под стол. Короче, ёж под столом.

[@heavis]

Единственная обратная связь, которую я могу тут дать: даже еж спать ушёл, автор, высыпайся!

[@JonDFG]

Что за программа?

[@Profimatika_vyshmat]

GoodNotes

[@Сергей-м1н8ъ]

Без ежа ничего не понятно.

[@bigsiege7684]

С ежом бы максимум до 2 ночи задержался.

[@dadyrole]

5:45😂

[@andreiantonov7303]

*решение 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]

@@andreiantonov7303 на моменте разложения суммы неверно, так как это оба расходящихся ряда)

[@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).

[@crazycat1503]

​@@Profimatika_vyshmat если пропустить это действие, то будет верное преобразование в сумму f(n)-f(n-1)/n

[@skatina2477]

У тебя ряд не сходится абсолютно, при этом в ходе решения ты переставлял его члены. Решение не верное)

[@Profimatika_vyshmat]

Изначальный ряд сходится абсолютно, я это показал в процессе решения)