2014 dxdy logo

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

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




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


23/07/08
10910
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
10910
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
11838
Россия, Москва
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
11838
Россия, Москва

(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
9180
Цюрих

(Оффтоп)

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
11838
Россия, Москва
Днём решил добить до $10^{12}$, запустил в 4 потока, только что завершилось.
Все результаты mihaild (чуть опередил) подтверждаю, полностью совпадают с моими.
Не ожидал что встретятся с младшей 9.

(Оффтоп)

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

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


16/07/14
9180
Цюрих

(Оффтоп)

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

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


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

(Оффтоп)

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

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

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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