2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение10.06.2017, 23:38 
Заслуженный участник
Аватара пользователя


23/07/08
10893
Crna Gora
Спасибо! Для пятёрок видно, что если не $40$, то $40\pm 9n$.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 01:28 
Аватара пользователя


01/12/11

8634
Мне только что подсказали добрые люди, что максимальная длина цепочки не превосходит 8.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 01:41 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Добрые люди это как-то обосновали?

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 08:28 
Заслуженный участник
Аватара пользователя


23/07/08
10893
Crna Gora
Что цепочки не могут быть длинными, видно из таких соображений.
Рассмотрим числа, которые отличаются только двумя последними цифрами, а сумма цифр $S$ у них одна и та же. Типа: $1027, 1036, 1045, 1054$ и т.д. Соседние отличаются на $9$. Значит, остаток от деления числа из этой последовательности на $S$ будет то нечётным, то чётным — то есть, за исключением $2$, не простым.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 08:33 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Спасибо; понял.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 10:19 
Аватара пользователя


01/12/11

8634
Aritaborian в сообщении #1224174 писал(а):
Добрые люди это как-то обосновали?


Добрые Люди писал(а):
На данный момент можно лишь заметить, что есть ограничение на длину цепочек. Среди трёх и более последовательных чисел встречается делящееся на 3. Тогда сумма цифр тоже делится на 3, и это же верно для остатка от деления числа на сумму цифр. Значит, он равен 3 в этом случае. Из этого пока ничего не следует, но если тот же аргумент применить к девяти последовательным числам, то среди них найдётся делящееся на 9, и тогда остаток будет делиться на 9, не будучи простым. Значит, максимальная длина цепочки не превосходит 8. Эта оценка сверху, скорее всего, не лучшая.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 14:47 
Заслуженный участник


20/08/14
11688
Россия, Москва
svv в сообщении #1224154 писал(а):
Для пятёрок видно, что если не $40$, то $40\pm 9n$.
Наблюдение подтверждается и дальше, как и строгое соответствие суммы 40 и младшей цифры 3. Проверено до $5\cdot 10^{11}$. "Шестёрок" не найдено.

(Оптимизация)

К сожалению, использование этого наблюдения для ускорения вычислений результата не дало, хоть проверять $1/9$ чисел, хоть $1/5$ (для поиска "пятёрок"), скорость отличается на считанные проценты. Видимо неподходящие числа в обоих случаях отбрасываются достаточно рано/быстро. Может конечно я плохо накодил ... Ну и париться с асм64 и avx2 пока что лень, не та задача.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 14:51 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Dmitriy40, сколько машинного времени ушло на расколошмачивание этого объёма чисел? И если не секрет, ТТХ компьютера.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 15:08 
Заслуженный участник


20/08/14
11688
Россия, Москва

(Aritaborian)

Да не секрет: Intel Core i5 Haswell 4 ядра 3.7ГГц (остальное не влияет).
Программа на дельфи x32, без особых оптимизаций (только деление и взятие остатка оптимизировано на асме, дельфи для int64 чисел такую пургу компилит, мрак). Ну внутренний цикл перебора миллиона чисел чуток оптимизирован, не считает сумму цифр каждого числа, а использует предпросчитанные таблицы. А, да, цикл перебирает числа с шагом 5 - "пятёрки" не пропустятся, при обнаружении кандидата (а их где-то с один процент) область расширяется в обе стороны для определения реальной длины последовательности. Проверка чисел на простоту совсем тупая, делениями на простые до $\sqrt{x}$ (до ~50 тысяч делений на число вылезает). Переписывать вычислительный цикл на асм64 или avx2 лень (не вижу что можно этим сильно ускорить).
Счёт идёт примерно 18ч (несколько раз оптимизировал и перезапускал), в один поток.С увеличением чисел заметно затормаживается (на глаз - уже раза в 3 медленнее), очевидно проверка на простоту тормозит процесс.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 15:10 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли

(Dmitriy40)

Спасибо.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение11.06.2017, 22:47 
Заслуженный участник
Аватара пользователя


16/07/14
9094
Цюрих

(Оффтоп)

Dmitriy40 в сообщении #1224316 писал(а):
Переписывать вычислительный цикл на асм64 или avx2 лень (не вижу что можно этим сильно ускорить).
Основная часть тут - это собственно проверка на простоту, и ее можно было бы очень хорошо ускорить, если бы были SIMD инструкции для деления или хотя бы умножения 64-битных чисел. Но нету.


-- 11.06.2017, 23:01 --

svv в сообщении #1224191 писал(а):
Соседние отличаются на $9$. Значит, остаток от деления числа из этой последовательности на $S$ будет то нечётным, то чётным — то есть, за исключением $2$, не простым.
Кажется этот аргумент не покрывает случай, когда у числа в разряде десятков стоит $9$ (тогда у числа, на $9$ большего, сумма цифр другая).

-- 11.06.2017, 23:21 --

До $10^{12}$: (последняя цифры, сумма цифр, сколько раз встретилось): [(('0', 49), 6), (('0', 67), 1), (('1', 58), 13), (('2', 31), 3), (('2', 49), 16), (('3', 40), 42), (('4', 31), 4), (('4', 67), 2), (('9', 58), 3)].
Т.е. сумма цифр сравнима с $4$ по модулю $9$.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение12.06.2017, 00:01 
Заслуженный участник


20/08/14
11688
Россия, Москва
Днём решил добить до $10^{12}$, запустил в 4 потока, только что завершилось.
Все результаты mihaild (чуть опередил) подтверждаю, полностью совпадают с моими.
Не ожидал что встретятся с младшей 9.

(Оффтоп)

mihaild в сообщении #1224445 писал(а):
Основная часть тут - это собственно проверка на простоту, и ее можно было бы очень хорошо ускорить, если бы были SIMD инструкции для деления или хотя бы умножения 64-битных чисел. Но нету.
Именно. Хотя умножение и не спасло бы, эти методы замены деления недостаточно точные для целых чисел. Потому и не вижу что можно кардинально ускорить ассемблером или SIMD.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение12.06.2017, 00:59 
Заслуженный участник
Аватара пользователя


16/07/14
9094
Цюрих

(Оффтоп)

Dmitriy40 в сообщении #1224470 писал(а):
Хотя умножение и не спасло бы, эти методы замены деления недостаточно точные для целых чисел.
Т.к. мы работаем в $\mathbb{Z}_{2^{64}}$, то можно заменить деление на фиксированный набор чисел (список простых) умножением на обратные по модулю - для делящихся нацело получим правильный результат - в частности, что-то меньшее $\frac{2^{64}}{p}$, для не делящихся - что-то большее.
Теоретически это можно было бы ускорить с помощью GPU, но я под них писать не умею.

 Профиль  
                  
 
 Re: Как много последовательных чисел могут встретиться?
Сообщение09.08.2018, 19:04 
Заслуженный участник


20/08/14
11688
Россия, Москва

(Оффтоп)

mihaild в сообщении #1224492 писал(а):
Т.к. мы работаем в $\mathbb{Z}_{2^{64}}$, то можно заменить деление на фиксированный набор чисел (список простых) умножением на обратные по модулю - для делящихся нацело получим правильный результат - в частности, что-то меньшее $\frac{2^{64}}{p}$, для не делящихся - что-то большее.
Наконец-то дошли руки разобраться с этим, действительно работает, оказалось я не то обратное число брал. Был не прав выше про недостаточную точность. Теперь думаю как это прикрутить к AVX2 без 64 бит умножений, задача-минимум: уложиться в 40 тактов на простое число, чтобы обогнать обычное деление.
UPD. Ха! Реализовал внутренний цикл, анализатор говорит 1.2 такта на число! :D И думаю можно сэкономить одну команду и получить ровно такт на число. Осталось добавить кучку таблиц и начальные проверки.

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

Модератор: Модераторы



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

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


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

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