@PatientZero8 дек 2017 в 07:01

Короткое плечо совпадения

13 мин

18K

Математика *

Перевод

+34

Комментарии 26

@Sharapoff 8 дек 2017 в 08:16

Класс! Спасибо.
Что-то мне подсказывает, что у вас тут опечатка:
«Другими словами, в бесконечной серии попыток вероятность никогда не вытащить чёрный мяч равна 0»
Не 0, а 1.
Или я ошибаюсь?

@PatientZero 8 дек 2017 в 08:28

1, потому что рано или поздно его достанут из урны.

@PatientZero 8 дек 2017 в 09:08

Тьфу, я имел в виду ноль, конечно же.

@khim 8 дек 2017 в 18:17

О! Двойное отрицание! Его и в английском-то языке не любят, а уж в русском — так и подавно.

Вероястность того, что вы будете тянуть-тянуть, тянуть-тянуть, но так никогда и не вытащите чёрный мяч таки равна нулю…

@charypopper 8 дек 2017 в 22:19

i can't get no satisfaction) RS
We don't need no education) PF

@Oize 8 дек 2017 в 08:27

Если честно, где-то в середине я перестал понимать происходящее, но разве тут не очевидно, что это могут быть только квадраты простых чисел?
Может быть проще рассмотреть формулу p^2 — 1 = n!, где p — простое число.
P.S. В комментариях есть поддержка формул?

@valemak 8 дек 2017 в 10:07

Насчёт формул в комментариях не знаю (в статьи вроде добавили что-то), но для показателя степени можно воспользоваться тегом <sup>

p² — 1 = n!

@aamonster 9 дек 2017 в 08:14

Не, с простыми — не очевидно. p не делится на числа от 2 до n, но почему бы ему не делиться на числа больше n? (От n+1 до sqrt(n!) много чисел)

@vin2809 8 дек 2017 в 09:02

Большое спасибо за работу. Интересно, а есть практическое применение этой теории?

@Bookvarenko 8 дек 2017 в 10:03

В кодировании наверно и декодировании. Или в шифровании и расшифровке. Ну, так в кино про Рамануджана показывали.

@Pentoxide 8 дек 2017 в 12:05

У вас ~~ус отклеился~~ синяя и оранжевая линии с графиков пропали.

Чтиво занятное. «Вероятность встретить ч-л на бесконечности стремится к числу между 0 и 1» — вот это пожалуй самое сильное.

@GarryC 8 дек 2017 в 13:55

Может на этом пути:
n!+1 = m'^2, где m'=2*m+1, тогда
n!+1=(2*m+1)^2=4*m^2+4*m+1
n!=4*m^2+4*m=4*m*(m+1)
Известные случаи 24=4*2*3 120=4*5*6(1*2*3) 5040=4*35(7*5)*36(1*2*3*6)
В общем случае n!/4=1*2*3*5*...*(n-1)*n = m*(m+1)
то есть сомножители m и m+1 набираются из чисел от 2 до n,
можно доказать, что n и n-1 должны входить в разные сомножители, но что делать дальше, я пока не придумал.

@GarryC 8 дек 2017 в 14:55

Ага, тогда, если n — четное, решение невозможно, поскольку один из сомножителей нечетный и в него не может войти ни одно из четных чисел, тогда все четные должны быть в одном сомножителе и он точно будет намного больше, чем второй, и даже отсутствие 4 не изменит ситуацию, начиная с n>=6.

@standy 8 дек 2017 в 19:52

Это сработало бы если бы числа 1..n нельзя было бы делить

@erwins22 8 дек 2017 в 17:06

abc гипотеза
n!+1=p^2

n! >> prime(n) prime — праймориал или произведение всех простых чисел меньших n
для 11 n!> (prime(11))^2

значит
p^2 <= K*p*prime(n)<=K*p^(1+eps)

т.е. существует такой eps что при больших значениях уравнение не будет выполняться

насколько я помню верно когда eps >0,5

т.е. досточно проверить для первых 12, дальше не будет

@WFF 8 дек 2017 в 17:21

n!+1 не делится нацело ни на одно из чисел 1..n, т.е. квадрат должен быть произведением простых чисел

@standy 8 дек 2017 в 19:33

А почему он не может быть произведением 4х простых чисел > n ?

@Starche 8 дек 2017 в 21:37

ru.wikipedia.org/wiki/Задача_Брокара
Нормально так человек издевается над подписчиками. Давайте, мол, возьмём нерешённую задачу математики, и дадим людям поразмышять

@honor8 11 дек 2017 в 14:06

Давайте поразмышляем, можно ли упростить :) Из очевидного (что дано):

a_n-1 * n + 1 оканчивается на 01 при a₁ = 1 и n > 9
(a_m-1 + 50)² оканчивается на 01 при a₁ = 49 и a₁ = 51

n-факториал быстро растёт, и для каждого значения a_n+5 в следующем разряде перед окончанием 01 будет стоять нуль. Как много существует значений функции m² и значений функции n! + 1 при равном порядке, у которых будут совпадать окончания? Будет ли уменьшаться количество значений с одинаковым окончанием для каждой функции при равном порядке?

@nizkopal 8 дек 2017 в 21:44

Спасибо, очень интересно было размять мозги в пятницу вечером. :)

Единственное, тут слово потерялось:

Являются ли 4, 5 и 7 единственными значениями n!, которые на 1 квадрата целого числа?

Видимо: на 1 меньше квадрата целого числа.

@michael_v89 9 дек 2017 в 11:34

Мне кажется, тут надо с комбинаторики начинать.

n! + 1 = m^2
n! = m^2 - 1
n! = (m + 1) * (m - 1)

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

Таким образом, число факториала должно быть нечетным, потому что единица не считается, и остается четное число множителей. 4 работает из-за маленьких значений, когда лишний множитель 2 не дает столь большого расхождения. Скорее всего, четных чисел с таким свойством больше нет, потому что при добавлении любой пары множителей расхождение будет увеличиваться. Для нечетных чисел равновесие сохраняется один раз, добавлением большего нового множителя к меньшему предыдущему сочетанию, а меньшего к большему, но в дальнейшем расхождение тоже становится гораздо больше 2.

Если разделить оба произведения на 2, то они должны отличаться на 1. Это невозможно, если в обоих произведениях 2 и более четных чисел. Это как раз начинается после 7. Если в одном произведении только нечетные, то тоже невозможно, так как будет с одной стороны нецелое число, а с другой целое. Думаю, можно как-то доказать, что если в одном из произведений оставить только 1 четное число, то для всех возможных вариантов расхождение после деления на 2 будет больше 1.

Минимальные варианты:

2 * 3 = 6 | 4 = 4 | 2

2 * 5 = 10 | 3 * 4 = 12 | 2

2 * 3 * 5 = 30 | 4 * 6 = 24 | 6
2 * 3 * 4 = 24 | 5 * 6 = 30 | 6

2 * 5 * 7 = 70 | 3 * 4 * 6 = 72 | 2

2 * 3 * 5 * 7 = 210 | 4 * 6 * 8 = 192 | 18
2 * 3 * 4 * 8 = 192 | 5 * 6 * 7 = 210 | 18

3 * 5 * 6 * 7 = 630 | 2 * 4 * 8 * 9 = 576 | 54
3 * 4 * 6 * 8 = 576 | 2 * 5 * 7 * 9 = 630 | 54

2 * 4 * 5 * 6 * 8 = 1920 | 3 * 7 * 9 * 10 = 1890 | 30
2 * 3 * 5 * 7 * 9 = 1890 | 4 * 6 * 8 * 10 = 1920 | 30
2 * 3 * 4 * 8 * 10 = 1920 | 5 * 6 * 7 * 9 = 1890 | 30

3 * 5 * 6 * 7 * 10 = 6300 | 2 * 4 * 8 * 9 * 11 = 6336 | 36
3 * 4 * 6 * 8 * 11 = 6336 | 2 * 5 * 7 * 9 * 10 = 6300 | 36

2 * 4 * 5 * 6 * 9 * 10 = 21600 | 3 * 7 * 8 * 11 * 12 = 22176 | 576
2 * 3 * 6 * 7 * 8 * 11 = 22176 | 4 * 5 * 9 * 10 * 12 = 21600 | 576
2 * 3 * 5 * 8 * 9 * 10 = 21600 | 4 * 6 * 7 * 11 * 12 = 22176 | 576
2 * 3 * 5 * 6 * 10 * 12 = 21600 | 4 * 7 * 8 * 9 * 11 = 22176 | 576
2 * 3 * 4 * 7 * 11 * 12 = 22176 | 5 * 6 * 8 * 9 * 10 = 21600 | 576

2 * 3 * 4 * 5 * 6 * 10 * 11 = 79200 | 7 * 8 * 9 * 12 * 13 = 78624 | 576
3 * 5 * 6 * 8 * 10 * 11 = 79200 | 2 * 4 * 7 * 9 * 12 * 13 = 78624 | 576
3 * 4 * 7 * 8 * 9 * 13 = 78624 | 2 * 5 * 6 * 10 * 11 * 12 = 79200 | 576
3 * 4 * 6 * 7 * 12 * 13 = 78624 | 2 * 5 * 8 * 9 * 10 * 11 = 79200 | 576
3 * 4 * 5 * 10 * 11 * 12 = 79200 | 2 * 6 * 7 * 8 * 9 * 13 = 78624 | 576

840
6120
24480
20160
93696
420480
...

Что интересно, для четных и нечетных веток расхождения возрастают, с единственным исключением. Возможно дальше тоже есть, но судя по динамике маловерятно.

четные:
2 6 18 30 576 840 24480 93696

нечетные:
2 2 54 36 576 6120 20160 420480

код

<?php

$arr = [2,3,4];

$minDiff = 1000000000;
foreach (getCombinations($arr, (int)(count($arr)/2)) as $variant) {

    list($a, $b) = $variant;

    $ma = getMult($a);
    $mb = getMult($b);
    $diff = abs($mb - $ma);

    if ($diff < $minDiff) $minDiff = $diff;

    if ($diff == 2) {
        echo printArr($a) . ' | ' . printArr($b) . ' | ' . $diff;
        echo PHP_EOL;
    }
}
echo 'Min diff: ' . $minDiff;
echo PHP_EOL;
return;

function printArr($arr)
{
    return implode(' * ', $arr) . ' = ' . getMult($arr);
}

function getMult($arr)
{
    return array_reduce($arr, function ($e, $res) { return $res*$e; }, 1);
}

function getCombinations($items, $n)
{
    if ($n == 0) {
        yield [$items, []];
    } else {
        foreach ($items as $i => $el) {
            foreach (getCombinations(array_slice($items, $i+1), $n-1) as $variant) {
                yield [array_merge(array_slice($items, 0, $i), $variant[0]), array_merge([$el], $variant[1])];
            }
        }
    }
}

@vlanko 9 дек 2017 в 21:53

Воотще тут случай узнать у специалистов, как точно считали факториал триллиона. Или какие более простые методы?

@Nick_mentat 18 дек 2017 в 09:24

А можно сделать что-то типа такого и посмотреть на график разницы? Интересно, как выглядит.

if r * r != fac + 1
      println(n, "! + 1 - ", r, "^2 = ", fac + 1 - r^2)

@echo10 20 дек 2017 в 08:53

Проверьте числа. Вольфрам Альфа вычисляет так:

@ulilu1372 20 дек 2017 в 08:53

В факториале по крайней мере один простой делитель — самый большой — всегда присутствует только один раз.

В факториале любой делитель присутствует только один раз, нет?
И как все-таки это утверждение связано с постулатом Бертрана?

@Nick_mentat 20 дек 2017 в 09:12

Факториал — произведение всех чисел от единицы до входного, среди них для n больше 3 всегда будут присутствовать составные числа (например 4), которые содеражат простые делители, которые уже были среди предыдущих чисел на числовой оси: 4! -> 2, 2, 2, 3 — двойка входит трижды. Также и остальные. Если бы не было правила Бертрана, то можно было бы сказать что мы находим такое простое число а, такое что между а и 2а нет других простых. Тогда взяв факториал (2а)! мы бы получили что множитель а входит в него дважды, т.е. доказательство не состоялось — требование содержания парного числа множителей не даёт нам никакой новой информации. Но с правилом Бертрана мы знаем что такое простое число не существует.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий