2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Интересная последовательность
Сообщение21.03.2019, 13:42 
Аватара пользователя


01/06/12
895
Adelaide, Australia
mihaild
Отличные результаты! Вы говорили что цикл для а=10 начинается с 40? А в таблице 5

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение21.03.2019, 14:03 
Заслуженный участник
Аватара пользователя


16/07/14
3010
Москва
Да, плохо написал. Это на самом деле первое простое число в цикле (и его позиция).

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение21.03.2019, 15:31 
Заслуженный участник


20/08/14
5590
Россия, Москва
Вот цикл для a=10 у меня: ... 1281, 640, 320, 160, 80, <40, 20, 10, 5, 35, 17, 299, ..., 10401, 5200, 2600, 1300, 650, 325, 162, 81>, 40, 20, 10, 5, 35, ...
И цикл начинается с позиции 39389, в которой стоит число 40.
Наибольшее число было из 3873 цифр.

Давайте уже договоримся что именно считать последовательностью: все числа или только простые среди них. В начальном сообщении темы указано считать все, вы же оба иногда учитываете только простые, как например в начальной позиции цикла для a=10 выше. Бардак.

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение22.03.2019, 00:00 
Аватара пользователя


01/06/12
895
Adelaide, Australia
Dmitriy40
Я предлагаю считать все числа.

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение22.03.2019, 21:43 
Заслуженный участник
Аватара пользователя


16/07/14
3010
Москва
https://github.com/mihaild/dxdy/tree/master/seq - код подсчета и последовательности простых для некоторых чисел
Число простых среди первых членов последовательности для $a = 6$:
Изображение

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение23.03.2019, 07:47 
Аватара пользователя


01/06/12
895
Adelaide, Australia
mihaild, спасибо за код и результаты. Мои результаты совпадают с вашими. Я не знал что в Python можно использовать такие огромные числа - это очень удобно.

Получился очень интересный график для а=6. Интересно почему много простых в начале и в конце? Подозреваю что это все маленькие простые, которых больше шансов случайно встретить, а в середине редкие большие простые.

Что будем дальше делать? Хорошо бы отправить в OEIS, но в каком виде? Еще появились новые вопросы:

1. Как доказать что будет бесконечный цикл?
2. Можно ли ускорить подсчет элементов? Например если у нас число вида $a*2^b$ то можно перейти до $a$.
3. Какой самый длинный подъем - цепочка простых подряд?
4. Какой самый длинный спуск - цепочка составных подряд?
5. Сколько разных циклов возможно для одного а и разных стартовых значений? Пока больше 3 не видел.
6. Почему последовательность имеет такое хаотичное поведение? Соседние а могут вести себя совсем по разному. Что у нее общего с последовательностью Коллатза?

 Профиль  
                  
 
 
Сообщение23.03.2019, 09:09 
Аватара пользователя


10/10/18
393
At Home
Someone в сообщении #1383144 писал(а):
У Д. Кнута мне попадался такой алгоритм поиска длины периода последовательности, задаваемой формулой $a_{n+1}=f(a_n)$...
В книге Уоррена Алгоритмические трюки для программистов (в конце главы 5, с.95-97 русского издания 2003 года) описан алгоритм Госпера (также со ссылкой на том 2 Кнута), который лучше. Там объёмно, вот, в интернете есть:
Cycle detection писал(а):
Gosper's algorithm

R. W. Gosper's algorithm[10][11] finds the period but not the starting point of the first cycle. Its main feature is that it never backs up to reevaluate the generator function, and is economical in both space and time. For example, if it is known a priori that the generator function has a period of $2^{32}$ then 33 words is sufficient.

10: http://www.hackersdelight.org/hdcodetxt/loopdet.c.txt
11: http://www.inwap.com/pdp10/hbaker/hakmem/flows.html -- ITEM 132 (Gosper): LOOP DETECTOR

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение23.03.2019, 09:44 


16/08/05
915
Не очень понятно, как получаются разные циклы для одного значения $a$. Мне думается, в таком виде в OEIS не примут. Если это особенность того, что Вы считаете цикл из не простых чисел, то - надо всё-таки считать цикл из простых чисел, который вроде должен быть однозначен (однозначно безконечен).

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение23.03.2019, 13:43 
Аватара пользователя


01/06/12
895
Adelaide, Australia
dmd, для одной а, но разных стартовых значений получаются разные циклы. В этих циклах отличается длина и составные числа.

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение23.03.2019, 22:31 
Заслуженный участник
Аватара пользователя


16/07/14
3010
Москва
Переписал на плюсы и распараллелил: https://github.com/mihaild/dxdy/blob/ma ... rallel.cpp
Для $a = 9$ цикла среди первых 324000 элементов нет, а самое длинное встреченное там число состоит из 38155 десятичных цифр.
Для $a = 18$ цикла среди первых 196988 элементов (125 простых) нет, самое длинное число до этого момента из 38763 цифр.

Не думаю, что этой последовательности место в OEIS - слишком она странная, да и деление пополам нацело - не особо интересная операция.

Список простых для $a = 6$ (вместе с номером в последовательности; по списку простых вся последовательность восстанавливается элементарно) - https://github.com/mihaild/dxdy/blob/master/seq/logs/6

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение14.04.2019, 16:38 
Аватара пользователя


01/06/12
895
Adelaide, Australia
Carlos Rivera опубликовал задачу на своем сайте:

https://www.primepuzzles.net/puzzles/puzz_949.htm

 Профиль  
                  
 
 Re: Интересная последовательность
Сообщение20.04.2019, 15:40 
Аватара пользователя


01/06/12
895
Adelaide, Australia
Вышли результаты с сайта Rivera. Для оригинальной задачи никто цикл не нашел, хотя нашли цикл для других стартовых чисел как например 3251 и его множители.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group