Конструктор может собрать любую конфигурацию, которую можно собрать из произвольного количества глайдеров. Естественно, он не может собрать абсолютно любую конфигурацию.
Основная суть - ограничение верхнего количества глайдеров. Если есть что-нибудь, что можно собрать из, скажем, 10^100 глайдеров, это же самое можно собрать и из 15 глайдеров.
Для такого рода игр можно получить точное решение с помощью цепей Маркова. Для каждой клетки поля расписывается вероятность попасть на каждую другую клетку поля. Затем можно использовать получившуюся матрицу в уравнениях, например, можно записать уравнение на ожидаемое количество ходов до каждой клетки. В решении такого рода уравнений будут учтены, в том числе, и бесконечные циклы (игрок постоянно ходит по кругу).
В вашем анализе "максимальное число ходов" не имеет смысла. С увеличением размера выборки это число будет расти, как раз из-за наличия бесконечного цикла. Минимальное число ходов, скорее всего, соответствует точному значению. Для него большой выборки не нужно, достаточно один раз попасть на оптимальную последовательность ходов.
Вероятности при условии более частого попадания в отбрасывалку считаются сложнее, но для них тоже потенциально можно получить точное решение. Здесь уже придётся (насколько я понимаю) хранить позицию каждого игрока и "превосходство по отбрасываниям". Матрица в этом случае будет большая и, возможно, за приемлемое время не удастся получить точного решения. Но в этом случае можно получить очень близкое к точному приближённое решение, используя в качестве состояния позицию игрока и количество отбрасываний вплоть до какого-то N, скажем, 50. Вероятности таких состояний будут очень маленькие, а следовательно, и погрешность результата.
А именно: для человеческого уха наиболее гармоничны те интервалы, где частоты точно соотносятся как небольшие натуральные числа. Например, октава - самый консонирующий интервал - всегда имеет соотношение 2:1
Это не обязательно так. Автокорреляция и обертоны играют более важную роль.
Когда я выгляжу как супергерой, я и действую по-супергеройски — быстро и точно.
Для меня это выглядит как осозноваемый эффект плацебо. Если это работает - почему бы и не воспользоваться?
Вроде бы серьёзные намерения у конторы, серьезный бизнес (о чем упоминалось не раз в статье), я бы даже сказал, что серьёзнее деятельность в IT не найти - и при этом супергерои... Как потом к вам серьезно-то и по взрослому относится?
Один пункт про внешний вид для вас перечёркивает все остальные в плане серьёзного отношения?
Простите за занудство - а я всегда думал, что в кибербезе мозг - это главное, а то, как ты выглядишь - вообще роли не играет - ибо тебя никто и не видит толком, да и не должен.
И при этом вы утверждаете, что считаете, что внешний вид роли вообще не играет?
Для меня выглядит так, как будто на самом деле критерием серьёзности отношения для вас является именно внешний вид и позиционирование себя.
Не соглашусь с обоими аргументами (в том смысле, что не считаю их аргументами "против").
Если же ходов будет несколько - то это для детей неправильно.
В первой задаче в разделе про открытый шах правильных ходов несколько - по сути, любой ход слона является решением. Во второй задаче из этого же раздела, с ладьёй и двумя королями, ходов, дающих шах, тоже несколько.
А дети на этот момент знают что король шах дать не может. И это ребенку дополнительная сложность.
Похожий аргумент применим и к той самой первой задаче со слоном. Вы сами пишете:
Дело в том, что они до этого четко усвоили что шах дает та же фигура которая ходит. Хотя про это и не говорилось в явном виде, но они запоминают именно это.
То есть, здесь тоже есть та самая дополнительная сложность, которую ребёнку приходится преодолевать.
Вот я и предлагаю по-максимуму уменьшить барьер, который нужно преодолеть, чтобы увидеть открытый шах. Ставим задачу с королём и двумя ладьями, как во втором примере из раздела про октрытый шах (только наш король стоит вплотную к ладье).
А почему бы не начинать объяснение открытого шаха с задачи с двумя королями и ладьёй? Причём ещё можно поставить короля вплотную к ладье, чтобы сократить количество возможных вариантов хода ладьи. В таком случае, на мой взгляд, ребёнку будет проще догадаться, что именно нужно сделать.
Всё-таки, у ладьи остаются ходы только вдоль одной линии, ни один из которых не даёт шах, а королём в задачах на шах ребёнок ходить ещё не пробовал. Если попробует - почти все ходы короля сработают.
Юмор: у кого-нибудь есть на примете суперкомпьютер, чтобы прогнать программу до такого значения? И куда вообще записать информацию о таком количестве простых чисел?
Необязательно хранить информацию о всех предыдущих простых при исследовании простых чисел.
Промежутки между простыми изучались разными людьми. Вот, например, один ресурс про промежутки.
Можно рассматривать такие задачи и их решения с точки зрения теории множеств и формальной логики. В этом случае можно перевести на формальный язык имеющиеся в задаче высказывания и оперировать уже строгими выводами.
С предпосылкой, что существуют бегемоты, то есть ∃x (x∈Б), можно получить выражение ∃x (x∈И)⋀(x∈М), то есть существуют знатоки интегрального исчисления, любящие мороженое.
Потому что по модулю простых, на которые раскладывается модуль, эти числа имеют остатки (1,1); (1,0); (0,1); (1,-1); (-1,1); (-1,-1). При возведении в степень они не меняются (потому что экспонента нечётная).
Какое-то у Вас сложноватое аналитическое решение. Через рекурсию проще:
Пусть E(n|b) - условное мат. ожидание количества пулов, если последний шар чёрный, и E(n|w) - условное мат. ожидание кол-ва пулов, если последний шар белый. Пусть p - вероятность вытянуть белый шар.
E(1|b)=0, E(1|w)=1
E(n+1|b) = E(n) =E(n|b)*(1-p)+E(n|w)*p - если последний шар чёрный, то мат. ожидание такое же, как если бы шара не было.
E(n+1|w) = E(n,w)*p + (E(n,b)+1)*(1-p) = E(n)+(1-p) - если последний шар белый, то мат. ожидание не меняется, если до этого тоже был белый шар, и увеличивается на 1, если до этого был чёрный шар.
В добавок к этому, если умножение медленнее, чем сложение (при увеличении размера чисел, например) полиномы можно перемножать с помощью техник быстрого умножения. (ax+b)(cx+d)=((a+b)(c+d)-bd)x+(ac+bd). Здесь 3 умножения и 4 сложения/вычитания.
Также для совсем больших чисел есть вариант воспользоваться китайской теоремой об остатках. Умножение при этом становится той же сложности, что и сложение, но идут потери на операции взятия остатков. Я не знаю, будет ли такой вариант быстрее. Его уже нужно аккуратно реализовывать и сравнивать.
А ещё можно возводить не матрицу в степень, а характерестический многочлен. Например, матрица Q = [[0,1], [1,1]] имеет характерестический многочлен x^2-x-1, и, значит, Q^2-Q-E = 0.
Пользуясь этим, возводим x в нужную степень по модулю x^2-x-1, получаем многочлен вида ax+b, подставляем туда Q и получаем ответ. Перемножение двух матриц 2*2 — это 8 умножений и 6 сложений, перемножение двух двучленов по модулю x^2-x-1 — это 4 умножения и 3 сложения.
Формула умножения: (ax+b)(cx+d)=acx^2+(ad+bc)x+bd=ac(x+1)+(ad+bc)x+bd=(ac+ad+bc)x+(bd+ac).
В случае большего количества членов в рекуррентном соотношении находить степень матрицы с помощью характеристического многочлена становится ещё выгоднее.
К сожалению, использовать формулу Эйлера для разложения чисел на множители так просто не получится.
В общем случае, для вычисления σ(n) для произвольного n вам понадобятся все предыдущие значения σ, поскольку в начале рекурсивной формулы стоят σ(n-1) и σ(n-2). Даже если предположить, что какую-то часть из предыдущих значений σ можно вычислить более эффективно за счёт частичной факторизации, итоговая сложность O(n) не изменится.
Если я не ошибаюсь, есть алгоритм для подсчёта σ(n) за O(n^(2/3) (log log n)^(1/3)). (Такой точно есть для Φ(n), суммы φ(i) для 1<=i<=n, и для некоторых других мультипликативных функций). Но даже этот метод сложнее, чем простой перебор всех делителей до n^(1/2).
Пока что для нахождения x и y, таких что x^2=y^2 (mod n) и x!=y, ничего лучше общего метода решета числового поля не придумали.
Можете ли вы использовать ваши наработки для разложения, например, вот этого числа?
Пожалуйста.
По ссылке — инструмент разложения на множители, использующий WebAssembly.
Раскладывает ваше число за 0.1 секунды, сразу после отпускания кнопки «Factor».
Использует общеизвестные метод квадратичного решета и метод эллиптических кривых.
1) Насколько обоснована замена (2n)^(1-s) на (2n-1)^(1-s) в равенстве перед (5)? Это всё выражение ведь стоит под знаком предела, а мы делаем замену в одной его части.
2) Как появилось равенство (8)?
Конструктор может собрать любую конфигурацию, которую можно собрать из произвольного количества глайдеров. Естественно, он не может собрать абсолютно любую конфигурацию.
Основная суть - ограничение верхнего количества глайдеров. Если есть что-нибудь, что можно собрать из, скажем, 10^100 глайдеров, это же самое можно собрать и из 15 глайдеров.
Можно посмотреть на вики: https://conwaylife.com/wiki/Main_Page
Самые интересные по мнению сообщества начальные конфигурации участвуют в небольшом конкурсе "Pattern of the Year": https://conwaylife.com/wiki/Pattern_of_the_Year
Для такого рода игр можно получить точное решение с помощью цепей Маркова. Для каждой клетки поля расписывается вероятность попасть на каждую другую клетку поля. Затем можно использовать получившуюся матрицу в уравнениях, например, можно записать уравнение на ожидаемое количество ходов до каждой клетки. В решении такого рода уравнений будут учтены, в том числе, и бесконечные циклы (игрок постоянно ходит по кругу).
В вашем анализе "максимальное число ходов" не имеет смысла. С увеличением размера выборки это число будет расти, как раз из-за наличия бесконечного цикла.
Минимальное число ходов, скорее всего, соответствует точному значению. Для него большой выборки не нужно, достаточно один раз попасть на оптимальную последовательность ходов.
Вероятности при условии более частого попадания в отбрасывалку считаются сложнее, но для них тоже потенциально можно получить точное решение. Здесь уже придётся (насколько я понимаю) хранить позицию каждого игрока и "превосходство по отбрасываниям". Матрица в этом случае будет большая и, возможно, за приемлемое время не удастся получить точного решения. Но в этом случае можно получить очень близкое к точному приближённое решение, используя в качестве состояния позицию игрока и количество отбрасываний вплоть до какого-то N, скажем, 50. Вероятности таких состояний будут очень маленькие, а следовательно, и погрешность результата.
Это не обязательно так. Автокорреляция и обертоны играют более важную роль.
https://www.youtube.com/watch?v=wg5QcF2akzQ
А вы слышали про Scala?
Там есть, по сути, всё, что нужно для любых экспериментов с музыкальными строями. А ещё в некоторых плагинах и DAW есть поддержка файлов .scl.
Для меня это выглядит как осозноваемый эффект плацебо. Если это работает - почему бы и не воспользоваться?
Один пункт про внешний вид для вас перечёркивает все остальные в плане серьёзного отношения?
И при этом вы утверждаете, что считаете, что внешний вид роли вообще не играет?
Для меня выглядит так, как будто на самом деле критерием серьёзности отношения для вас является именно внешний вид и позиционирование себя.
Не соглашусь с обоими аргументами (в том смысле, что не считаю их аргументами "против").
В первой задаче в разделе про открытый шах правильных ходов несколько - по сути, любой ход слона является решением. Во второй задаче из этого же раздела, с ладьёй и двумя королями, ходов, дающих шах, тоже несколько.
Похожий аргумент применим и к той самой первой задаче со слоном. Вы сами пишете:
То есть, здесь тоже есть та самая дополнительная сложность, которую ребёнку приходится преодолевать.
Вот я и предлагаю по-максимуму уменьшить барьер, который нужно преодолеть, чтобы увидеть открытый шах. Ставим задачу с королём и двумя ладьями, как во втором примере из раздела про октрытый шах (только наш король стоит вплотную к ладье).
А почему бы не начинать объяснение открытого шаха с задачи с двумя королями и ладьёй? Причём ещё можно поставить короля вплотную к ладье, чтобы сократить количество возможных вариантов хода ладьи. В таком случае, на мой взгляд, ребёнку будет проще догадаться, что именно нужно сделать.
Всё-таки, у ладьи остаются ходы только вдоль одной линии, ни один из которых не даёт шах, а королём в задачах на шах ребёнок ходить ещё не пробовал. Если попробует - почти все ходы короля сработают.
Необязательно хранить информацию о всех предыдущих простых при исследовании простых чисел.
Промежутки между простыми изучались разными людьми. Вот, например, один ресурс про промежутки.
Можно рассматривать такие задачи и их решения с точки зрения теории множеств и формальной логики. В этом случае можно перевести на формальный язык имеющиеся в задаче высказывания и оперировать уже строгими выводами.
Бегемоты знают интегральное исчисление. ∀x (x∈Б)→(x∈И)
Все бегемоты любят мороженое. ∀x (x∈Б)→(x∈М)
С предпосылкой, что существуют бегемоты, то есть ∃x (x∈Б), можно получить выражение ∃x (x∈И)⋀(x∈М), то есть существуют знатоки интегрального исчисления, любящие мороженое.
Для случайных супов размером 16*16 с заполнением 50% собирается огромная статистика здесь:
https://catagolue.hatsya.com/statistics
Потому что по модулю простых, на которые раскладывается модуль, эти числа имеют остатки (1,1); (1,0); (0,1); (1,-1); (-1,1); (-1,-1). При возведении в степень они не меняются (потому что экспонента нечётная).
Какое-то у Вас сложноватое аналитическое решение. Через рекурсию проще:
Пусть E(n|b) - условное мат. ожидание количества пулов, если последний шар чёрный, и E(n|w) - условное мат. ожидание кол-ва пулов, если последний шар белый. Пусть p - вероятность вытянуть белый шар.
E(1|b)=0, E(1|w)=1
E(n+1|b) = E(n) =E(n|b)*(1-p)+E(n|w)*p - если последний шар чёрный, то мат. ожидание такое же, как если бы шара не было.
E(n+1|w) = E(n,w)*p + (E(n,b)+1)*(1-p) = E(n)+(1-p) - если последний шар белый, то мат. ожидание не меняется, если до этого тоже был белый шар, и увеличивается на 1, если до этого был чёрный шар.
E(n+1)=E(n+1|b)*(1-p)+E(n+1|w)*p=E(n)*(1-p)+E(n)*p+(1-p)*p=E(n)+p(1-p)
Учитывая E(1)=p, получаем E(n)=p+(n-1)p(1-p)=p^2+np(1-p)
E(20)=4/49+20*2/7*5/7=204/49
В добавок к этому, если умножение медленнее, чем сложение (при увеличении размера чисел, например) полиномы можно перемножать с помощью техник быстрого умножения. (ax+b)(cx+d)=((a+b)(c+d)-bd)x+(ac+bd). Здесь 3 умножения и 4 сложения/вычитания.
Также для совсем больших чисел есть вариант воспользоваться китайской теоремой об остатках. Умножение при этом становится той же сложности, что и сложение, но идут потери на операции взятия остатков. Я не знаю, будет ли такой вариант быстрее. Его уже нужно аккуратно реализовывать и сравнивать.
Пользуясь этим, возводим x в нужную степень по модулю x^2-x-1, получаем многочлен вида ax+b, подставляем туда Q и получаем ответ. Перемножение двух матриц 2*2 — это 8 умножений и 6 сложений, перемножение двух двучленов по модулю x^2-x-1 — это 4 умножения и 3 сложения.
Формула умножения: (ax+b)(cx+d)=acx^2+(ad+bc)x+bd=ac(x+1)+(ad+bc)x+bd=(ac+ad+bc)x+(bd+ac).
В случае большего количества членов в рекуррентном соотношении находить степень матрицы с помощью характеристического многочлена становится ещё выгоднее.
В общем случае, для вычисления σ(n) для произвольного n вам понадобятся все предыдущие значения σ, поскольку в начале рекурсивной формулы стоят σ(n-1) и σ(n-2). Даже если предположить, что какую-то часть из предыдущих значений σ можно вычислить более эффективно за счёт частичной факторизации, итоговая сложность O(n) не изменится.
Если я не ошибаюсь, есть алгоритм для подсчёта σ(n) за O(n^(2/3) (log log n)^(1/3)). (Такой точно есть для Φ(n), суммы φ(i) для 1<=i<=n, и для некоторых других мультипликативных функций). Но даже этот метод сложнее, чем простой перебор всех делителей до n^(1/2).
Пока что для нахождения x и y, таких что x^2=y^2 (mod n) и x!=y, ничего лучше общего метода решета числового поля не придумали.
Можете ли вы использовать ваши наработки для разложения, например, вот этого числа?
По ссылке — инструмент разложения на множители, использующий WebAssembly.
Раскладывает ваше число за 0.1 секунды, сразу после отпускания кнопки «Factor».
Использует общеизвестные метод квадратичного решета и метод эллиптических кривых.
121 241049 900967 702364 547631 496025 805899 235111 234517 297337 146822 316495 235876 616358 461674 527872 011636 924497 562925 302808 453429 142214 349122 818616 057572 516600 366274 212211 003166 727994 259866 706386 156211 164560 608980 088597 778945 129523 261123 792515 417395 909528 108341 327263 818561 533179 501150 287508 476636 494044 662023 007181 337632 016581 807661 487611 433267 070116 890566 867316 324094 483877 934846 551653 230100 889301 992016 327007 146157 037533 097745 501651 =11010 951362 210610 653340 531695 680978 537253 573832 466721 540755 129920 598632 708162 341812 112676 386546 123929 261373 102107 778116 365812 718595 176904 357730 626934 890548 662144 814272 302138 029201 382092 873434 079428 497949 747137 334911 ×
11010 951362 210610 653340 531695 680978 537253 573832 466721 540755 129920 598632 708162 341812 112676 386546 123929 261373 308910 479856 522097 310652 382585 965473 524887 805788 239641 958586 357190 657469 162428 027337 296974 760058 561894 727341)
Первые 107 десятичных знаков множителей одинаковые. Видимо, ваш генератор случайных чисел генерирует не настолько уж и случайные числа.
2) Как появилось равенство (8)?