19.04.2022 23:04
Ramayasket 16 1800 Источник

Введение

UPD: После публикации статьи в комментариях выяснилось, что представляемое разбиение не является новым, оно известно как последовательность Пиллаи. С учётом "вновь открывшихся данных", эту статью можно рассматривать как пример удавшегося обращения к сообществу Хабр за советом. Я выражаю признательность @harius за ценную подсказку.

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

В статье предлагается способ выразить натуральное число через уникальное множество простых чисел (включая единицу), сложение которых даёт исходное число. Такую композицию будем называть аддитивной.

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

Аддитивная композиция

Введём понятие примитивного числа. Натуральное число будем называть примитивным, если оно является простым или равно единице. Мы будем раскладывать натуральное число на примитивные по следующему правилу:

Пусть n - натуральное число. Найдём наибольшее примитивное число n_0такое что n_0 < n. Вычислим i_1 = n-n_0. Далее аналогично найдём наибольшее примитивное число n_1такое что n_1 \le i_1. Будем повторять эти действия до тех пор, пока n_{k+1}не окажется равно нулю; тогда n = n_0 + n_1 + \dots + n_kМножество P(n) = \{n_0, n_1, \cdots, n_k\}будем называть аддитивной композицией числа n.

Аддитивное разбиение, как и мультипликативное, является однозначным для каждого n. Разбиение для первых 50 чисел выглядит так:

1 = 1*
2 = 1+1
3 = 2+1
4 = 3+1
5 = 3+2
6 = 5+1
7 = 5+2
8 = 7+1
9 = 7+2
10 = 7+3

11 = 7+3+1
12 = 11+1
13 = 11+2
14 = 13+1
15 = 13+2
16 = 13+3
17 = 13+3+1
18 = 17+1
19 = 17+2
20 = 19+1

21 = 19+2
22 = 19+3
23 = 19+3+1
24 = 23+1
25 = 23+2
26 = 23+3
27 = 23+3+1
28 = 23+5
29 = 23+5+1
30 = 29+1

31 = 29+2
32 = 31+1
33 = 31+2
34 = 31+3
35 = 31+3+1
36 = 31+5
37 = 31+5+1
38 = 37+1
39 = 37+2
40 = 37+3

41 = 37+3+1
42 = 41+1
43 = 41+2
44 = 43+1
45 = 43+2
46 = 43+3
47 = 43+3+1
48 = 47+1
49 = 47+2
50 = 47+3

* данное разбиение является исключением, оно считается не строго по формуле

Единственным случаем, когда в P(n)присутствуют одинаковые числа, является 2 = 1+1, далее числа не повторяются. Предположительно, это объясняется тем, что между nи 2nесть как минимум одно простое число n < p < 2n.

Как видно, размер для первых чисел (кроме единицы) равен двум или трём. Первая композиция длиной 4 появляется при n=1354(1354 = 1327+23+3+1), первым простым числом с композицией длиной 4 является n=2010881(2010881 = 2010733+139+7+2).

И на этом всё! Все числа до одного триллиона включительно разбиваются не более чем на 4 числа. Первый из немедленно возникших вопросов – а не все ли вообще натуральные числа можно разбить не более чем на 4 примитивных числа?

Предположим, есть два простых числа m_1и m_2, такие что m_2 = m_1 + 1354. Тогда разбиение m_2будет m_1+1327+23+3+1. По всей видимости, "запретных" расстояний между простыми числами нет, и рано или поздно встретится расстояние 1354 и второе число будет иметь композицию длиной 5. Насколько далеко находится первая такая пара? Википедия говорит, что расстояние 1356 где-то в районе четырёхсот квадриллионов.

Юмор: у кого-нибудь есть на примете суперкомпьютер, чтобы прогнать программу до такого значения? И куда вообще записать информацию о таком количестве простых чисел? Для записи чисел до триллиона использовался битовый массив размером 116 Гигабайт.

Второе интересное свойство заключается в том, что для простых чисел до триллиона все композиции длиной 4 заканчиваются на 7+2. В зависимости от расстояния между простыми числами, последние три числа выглядят так (расстояние = x+7+2):

122 = 113+7+2
148 = 139+7+2
190 = 181+7+2
208 = 199+7+2
220 = 211+7+2
250 = 241+7+2
292 = 283+7+2

302 = 293+7+2
326 = 317+7+2
346 = 337+7+2
418 = 409+7+2
430 = 421+7+2
476 = 467+7+2
532 = 523+7+2

Второй аналогичный вопрос: верно ли это для всех простых чисел с композицией длины 4?

Заключение

Идея аддитивной композиции родилась в процессе размышлений на тему: можно ли понять, каково следующее простое число, если известны все простые числа до него? Т.е. вычислять следующее простое число по простой формуле или алгоритму. Когда аддитивная композиция была сформулирована, естественным желанием было посчитать её на практике и посмотреть на результаты.

Цель статьи – подключить к исследованию других заинтересованных участников.

Комментарии (16)


  1. Alexandroppolus
    20.04.2022 00:03
    #24280441

    Зачем разбивать простые числа? Более логичным кажется, что простое состоит из одной "детали", как в случае с умножениями.


  1. Alek_roebuck
    20.04.2022 00:04
    #24280445

    Такую композицию можно называть мультипликативной, она очень хорошо известна и изучена.

    Хорошо известна и называется каноническим разложением (в смысле ОТА).

    а не все ли вообще натуральные числа можно разбить не более чем на 4 примитивных числа?

    В такой формулировке - да, все можно. Следует из уже доказанной тернарной гипотезы Гольдбаха. Более того, скорее всего, достаточно трех примитивных чисел, если верна обычная (бинарная) гипотеза Гольдбаха: двух - для четных чисел, а двух примитивных + любого примитивного, кроме двойки - для нечетных. Но вы, наверно, имели в виду разбиение по вашему правилу.


    1. Ramayasket Автор
      20.04.2022 00:05
      #24280449

      Да, именно по этому правилу.


  1. Pavgran
    20.04.2022 00:27
    #24280487
    +3

    Юмор: у кого-нибудь есть на примете суперкомпьютер, чтобы прогнать программу до такого значения? И куда вообще записать информацию о таком количестве простых чисел?

    Необязательно хранить информацию о всех предыдущих простых при исследовании простых чисел.

    Промежутки между простыми изучались разными людьми. Вот, например, один ресурс про промежутки.

    2805562883448464207=2 805562 883448 462853+1327+23+3+1


  1. celen
    20.04.2022 01:37
    #24280577
    +1

    Для записи чисел до триллиона использовался битовый массив размером 116 Гигабайт.

    Насколько я понял по ссылке, вы предлагаете заполнить элемент массива таким образом: A[p] = 1 если p простое число и 0 если составное. Размер массива это приблизительно подтверждает: 10^12 бит = 125 Гб.

    Почему не произвели очевидную оптимизацию по записи в массив только чисел, не делящихся на 2 3 5? Тогда надо будет учесть только числа, имеющие один из 8 остатков от деления на 30 : 1 7 11 13 17 19 23 29 . В этом случае каждый байт будет кодировать простоту 30 последовательных чисел и в итоге для триллиона будет нужно примерно 10^12/30 = 33 Гб. Очевидно, что 33 Гб гораздо лучше, чем 116.

    Дальше. Так как простые числа распределены примерно как Pr(n) = n/ln(n) где Pr(n) - число простых меньше n, очевидно, что промежутки между ними будут (в среднем) расти, а значит и размер вашей аддитивной композиции будет расти вплоть до бесконечности. Насколько быстро расти? Предлагаю оценку:

    Обозначим за сP(n) = |P(n)|. Дадим оценку: cP(n) = сP(ln(n)) + 1 . Обозначим за Pc(n) степенную башню экспонент: e^e^e^...^e n раз. Pc(cP(n)) = Pc(сP(ln(n)) + 1) = e^Pc(сP(ln(n))) . Поскольку n = e^ln(n), выходит, что cP - функция, обратная Pc , своеобразный степенно-башенный логарифм. То есть, что бы оценить зону, где большинство чисел будут иметь композицию длиной 4, Учитывая, что Pc(n) растет невообразимо быстро, можно утверждать, что где-то далеко-далеко в числовом ряду есть места, где большинство чисел раскладываются на композиции длиной 4, 5 или даже 139, но, правда, эти места уж очень далеко от нас (хотя и ближе, чем число Грэма). Разумеется, отдельные примеры длинных цепочек встретятся куда раньше.

    Наблюдение про 7+2 так же легко объясняется по вашему же построению. Вы хотите, фактически, что бы в результате суммы четырех простых чисел у вас получилось простое число. Очевидно, что последним будет 2. Предпоследним же должно быть некое простое число p такое, что p+2 составное; при этом чем меньше число p, тем больше у него шансов попасть в разложение. p = 7 самое маленькое нечетное простое, такое, что p+2 - составное число, так что шансов у него больше всего.


  1. paluke
    20.04.2022 07:23
    #24280785

    Проблема Гольдбаха?


    1. Deosis
      20.04.2022 07:26
      #24280789

      Сильно упрощенная версия, так как можно использовать единицу в разложении.


  1. harius
    20.04.2022 09:47
    #24281195

    Сабж уже изучался: https://en.wikipedia.org/wiki/Pillai_sequence

    TL;DR: a(5)=401429925999155061; a(6) "likely has hundreds of millions of digits"


    1. AxelLx
      20.04.2022 14:39
      #24282645

      Это немного другое. В последовательности Pillai для разложения числа на слагаемые разрешено использовать само число (если оно примитивно, разумеется).
      Но как оценка сверху вполне подходит, 401429925999155061 нельзя разложить на менее чем 5 слагаемых по правилам Ramayasket.


      1. Ramayasket Автор
        20.04.2022 14:40
        #24282647

        Как это использовать само число? Т.е. 11 = 11+?


        1. AxelLx
          20.04.2022 14:46
          #24282665

          Просто, 11 = 11. Разложение из одного слагаемого.


          1. edo1h
            20.04.2022 14:56
            #24282703

            ну это немного не то. тут интересно было именно разложение простых чисел на сумму других простых же чисел.


            1. AxelLx
              20.04.2022 15:01
              #24282721

              ну это немного не то.

              См. мой первый комментарий в этой ветке:
              Это немного другое.


      1. Ramayasket Автор
        20.04.2022 14:53
        #24282691

        Т.е. Вы хотите сказать, что в последовательности Пиллаи простые числа раскладываются на себя и всё? Написано "choose the first prime in the sum to be the largest prime p that is at most n", если "at most", то получается, что да?


        1. AxelLx
          20.04.2022 15:03
          #24282739

          Да, по аналогии с каноническим разложением на сомножители, разложение Pillai может состоять из одного элемента.


  1. AxelLx
    20.04.2022 14:46
    #24282663

    del