Поиск позиции квадрата числа в последовательности

@Whost · Регистрация: 13.02.2016

Студворк — интернет-сервис помощи студентам

Пытаюсь оптимизировать алгоритм для поиска простых чисел и возник вопрос в создании формулы, которая вычисляла бы позицию квадрата числа по позиции самого числа.
Ну, например для обычной последовательности(1, 2, 3, 4..) эта формула будет равна i^2 + 2 * i(то есть например у 2 позиция 1, следовательно 1^2 + 2 * 1 = 3, то есть позиция четырех.
С горем пополам(методом подбора) нашел формулу для последовательности (1, 3, 5, 7, 9... то есть последовательность без чисел кратных двум), она равна 2 * i^2 + 2 * i
Застрял на последовательности без чисел, кратных двум и трем (1, 5, 7, 11, 13, 17, 19...), тут уже перебором не справился, да и на трех мои проблемы не заканчиваются(нужно как минимум до 19).В математике я полный ноль, поэтому прошу хотя бы подсказать, в каком направлении стоит двигаться(что читать/гулить), чтоб разобраться во всем этом, либо объяснить как это все делается, если кто знает
Заранее спасибо.
P.S. отсчет позиций ведется с нуля

echs · 12.05.2016, 09:53

Whost
Не знаю, то ли вам нужно. Но все простые числа
следует искать на множестве $https://www.cyberforum.ru/cgi-bin/latex.cgi?6n\pm1$ (исключение для чисел 2 и 3)
n - натуральное число

Байт · 12.05.2016, 11:25

Сообщение от geh

все простые числа следует искать на множестве

Можно даже 30*к +-1 +-7 +-11 +-13, что дает некоторые вычислительные приемущества, Так как в каждой тридцатке таких чисел 8, а байте тоже 8 битов. Совпадение случайное, но удачное.

@Whost · 12.05.2016, 14:44 **[ТС]**

Можно даже в 210*K + 1, + 11, + 13 ...(всего 48) и даже в 2310*k (всего 480) и так до бесконечности и это не случайность. Я знаю как их искать, все что мне нужно это еще больше оптимизировать этот алгоритм, начиная искать число с позиции квадрата этого числа
P.S. я хочу применить этот алгоритм к последовательности 9699690 * k +- 1...(получится 1658880 чисел)

echs · 12.05.2016, 16:04

Whost
Вы знаете, однажды мне потребовался такой быстрый алгоритм.
Что я сделал? Создал файл, в котором поместил ровно 100 000 000
простых чисел. (Программа на VB 6.0 сделала его за 3 часа).
Зато потом мне не пришлось эти числа вычислять. Доли секунды и
число считано . ..

@Whost · 12.05.2016, 16:38 **[ТС]**

geh, да, я с вами полностью согласен, но дело в том что я делаю это не ради чисел, а ради максимальной скорости и просто ради интереса. Я пишу программу, смотрю время и начинаю делать еще более быстрый алгоритм. Что-то вроде небольшого хобби. Может когда-нибудь и рекорд поставлю)

Байт · 13.05.2016, 10:50

Сообщение от Whost

Может когда-нибудь и рекорд поставлю)

Сообщение от Whost

В математике я полный ноль,

Не думаю, что это вам удастся. Проблемы простых чисел завораживают многих. И не только нулей.
Но на форуме где-то было очень интересное обсуждение разных алгоритмов. По скорости и по целям. Рассматривалось 2 цели. 1. Проверить данное число на простоту. 2. Составить эратосфеново решето (список всех простых до как можно большего). Соответственно, для разных целей - разные алгоритмы. И довольно интересные. Элементарные (не значит, что простые, значит - не требующие введения сложных понятий и аппаратов)
Если не лень - поищите

Добавлено через 6 минут

Сообщение от Whost

Можно даже в 210*K + 1, + 11, + 13 ...(всего 48) и даже в 2310*k (всего 480) и так до бесконечности и это не случайность.

Можно. Но без толку. Хороший результат дает именно 30. Это оптимум.

Добавлено через 11 часов 32 минуты
Whost, Последовательность 1, 5, 7, 11... (2 перемешанные арифметические) задается формулой
a_n = 3*n + (3 - (-1)ⁿ)/2

Добавлено через 2 минуты
Выводится это из рекурентного воотношения a_n+2 - a_n = 6 с начальными условиями a₀ = 1, a₁ = 5

Добавлено через 9 минут
Если следовать этой методике, для 30 (отсутствие делимых на 2, 3, 5) рекурентное соотношение будет выглядеть так a_n+8 - a_n = 30, а начальных условий будет аж 8. Характеристическое уравнение q⁸ - 1 = 0 имеет 8 комплексных корней. Чтобы найти решение, придется изрядно попотеть, хотя там все линейно. Дальше - хуже. Однако программно решить эту задачу не должно быть принципиально сложно. Правда, кое-какие сведения из математики лишними не будут

@Whost · 13.05.2016, 13:34 **[ТС]**

Почему же без толку? Для 210 мы должны найти 1 и 47 первых простых чисел начиная с 11, получится 48 последовательностей, которые по сути можно впихнуть в 24(делать последовательности вида 210k +- a), что даст еще примерно 4% прирост производительности. Дальше уже да, смысла почти нет, но по идее некоторый прирост(1-2%) это еще будет давать(до числа 19, дальше уже еле дотягивает до 0.5%). Но я спрашивал немного другое, попробую еще раз объяснить:
Мы имеем последовательность 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49 ...
Число 5 стоит на позиции 1, число 25 (5^2) на позиции 8. Так вот, мне нужно придумать формулу, в которую я могу подставить 1 и получить 8 и так для каждого числа, то есть для 7, который находится на позиции 2, я должен получить 16, то есть позицию числа 49.
Проблема в том, что я понятия не имею, как составлять такие формулы, разве что методом подбора.

Байт · 13.05.2016, 15:05

Сообщение от Whost

Проблема в том, что я понятия не имею, как составлять такие формулы,

Я уже привел в посте 7 такую формулу

Сообщение от Байт

Whost, Последовательность 1, 5, 7, 11... (2 перемешанные арифметические) задается формулой an = 3*n + (3 - (-1)n)/2

и метод ее получения через рекурентные уравнения с начальными условиями.
Точнее, это формула общего члена исходной последовательности 1, 5, 7, 11...
Но из нее несложно получить и формулу для номера квадрата
a_n² = a_k.
Считаешь n известным и ищешь k.
Там могут возникнуть некоторые сложности с членом (-1)^k, но я думаю, они легко обходятся. Рассмотри несколько примеров и поймай закономерность.
Для начала k надо считать приближенно с точностью до 1/6. А потом прибавить - отнять эту 1/6. Я думаю, ее знак получится автоматом при округлении k до ближайшего целого.

@Whost · 13.05.2016, 16:42 **[ТС]**

Байт, спасибо, получилось! С (-1)^k не было проблем(k всегда четный, поэтому просто представил как 1)
Правда есть одна проблема: в конечной формуле - $https://www.cyberforum.ru/cgi-bin/latex.cgi?3n^2 + 1/2 + 3n - n(-1)^n$ есть 1/2 так что нужно либо делать две формулы: $https://www.cyberforum.ru/cgi-bin/latex.cgi?3n^2 + 1 + 3n - n(-1)^n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?3n^2 + 3n - n(-1)^n$ , либо переделывать эту. У меня получилось так $https://www.cyberforum.ru/cgi-bin/latex.cgi?3n ^ 2 + 1/2 - (-1) ^ n/2 + 3n - n( - 1) ^ n$ , но может есть способ сделать лучше?

Байт · 13.05.2016, 22:47

Сообщение от Whost

С (-1)^k не было проблем(k всегда четный, поэтому просто представил как 1)

А и правда! Чего-то мне в голову не пришло...

Сообщение от Whost

В математике я полный ноль,

Скорее всего это скромность и немножко кокетства (и то и другое - вполне простительно) Математические Нули как правило даже не задумываются об таких штуках. Увы! я тоже в этом деле отнюдь не мажор, просто чего-то нахватался, и что-то было интересно.
А простые числа, да, они завораживают. Вроде все так просто, на уровне арифметики 5-го класса. Но чем ближе к бесконечности (хороший пассаж - посмейтесь вместе со мной) тем все становится интересней.
Удачи вам, и не скучать!

@Whost · 14.05.2016, 08:28 **[ТС]**

Сообщение от Байт

Скорее всего это скромность и немножко кокетства (и то и другое - вполне простительно)

Считаю себя нулем, т.к. дальше школьной программы не ушел, а когда смотрю некоторые формулы и математические объяснения по тем же простым числам, то кроме случайного набора букв и цифр ничего не вижу.

Сообщение от Байт

Удачи вам, и не скучать!

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

Поиск позиции квадрата числа в последовательности

Решение

Решение

@Whost 30 / 30 / 22 Регистрация: 13.02.2016 Сообщений: 131
		1
	Поиск позиции квадрата числа в последовательности 11.05.2016, 21:43. Показов 1370. Ответов 11 Метки нет (Все метки) Пытаюсь оптимизировать алгоритм для поиска простых чисел и возник вопрос в создании формулы, которая вычисляла бы позицию квадрата числа по позиции самого числа. Ну, например для обычной последовательности(1, 2, 3, 4..) эта формула будет равна i^2 + 2 * i(то есть например у 2 позиция 1, следовательно 1^2 + 2 * 1 = 3, то есть позиция четырех. С горем пополам(методом подбора) нашел формулу для последовательности (1, 3, 5, 7, 9... то есть последовательность без чисел кратных двум), она равна 2 * i^2 + 2 * i Застрял на последовательности без чисел, кратных двум и трем (1, 5, 7, 11, 13, 17, 19...), тут уже перебором не справился, да и на трех мои проблемы не заканчиваются(нужно как минимум до 19).В математике я полный ноль, поэтому прошу хотя бы подсказать, в каком направлении стоит двигаться(что читать/гулить), чтоб разобраться во всем этом, либо объяснить как это все делается, если кто знает Заранее спасибо. P.S. отсчет позиций ведется с нуля 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	12.05.2016, 09:53	2
	Whost Не знаю, то ли вам нужно. Но все простые числа следует искать на множестве $https://www.cyberforum.ru/cgi-bin/latex.cgi?6n\pm1$ (исключение для чисел 2 и 3) n - натуральное число 0

Байт Диссидент 27495 / 17183 / 3784 Регистрация: 24.12.2010 Сообщений: 38,704
	12.05.2016, 11:25	3
	Сообщение от geh все простые числа следует искать на множестве Можно даже 30*к +-1 +-7 +-11 +-13, что дает некоторые вычислительные приемущества, Так как в каждой тридцатке таких чисел 8, а байте тоже 8 битов. Совпадение случайное, но удачное. 0

@Whost 30 / 30 / 22 Регистрация: 13.02.2016 Сообщений: 131
	12.05.2016, 14:44 [ТС]	4
	Можно даже в 210K + 1, + 11, + 13 ...(всего 48) и даже в 2310k (всего 480) и так до бесконечности и это не случайность. Я знаю как их искать, все что мне нужно это еще больше оптимизировать этот алгоритм, начиная искать число с позиции квадрата этого числа P.S. я хочу применить этот алгоритм к последовательности 9699690 * k +- 1...(получится 1658880 чисел) 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	12.05.2016, 16:04	5
	Whost Вы знаете, однажды мне потребовался такой быстрый алгоритм. Что я сделал? Создал файл, в котором поместил ровно 100 000 000 простых чисел. (Программа на VB 6.0 сделала его за 3 часа). Зато потом мне не пришлось эти числа вычислять. Доли секунды и число считано . .. 0

@Whost 30 / 30 / 22 Регистрация: 13.02.2016 Сообщений: 131
	12.05.2016, 16:38 [ТС]	6
	geh, да, я с вами полностью согласен, но дело в том что я делаю это не ради чисел, а ради максимальной скорости и просто ради интереса. Я пишу программу, смотрю время и начинаю делать еще более быстрый алгоритм. Что-то вроде небольшого хобби. Может когда-нибудь и рекорд поставлю) 0

Байт Диссидент 27495 / 17183 / 3784 Регистрация: 24.12.2010 Сообщений: 38,704
	13.05.2016, 10:50	7
	Сообщение было отмечено Whost как решение Решение Сообщение от Whost Может когда-нибудь и рекорд поставлю) Сообщение от Whost В математике я полный ноль, Не думаю, что это вам удастся. Проблемы простых чисел завораживают многих. И не только нулей. Но на форуме где-то было очень интересное обсуждение разных алгоритмов. По скорости и по целям. Рассматривалось 2 цели. 1. Проверить данное число на простоту. 2. Составить эратосфеново решето (список всех простых до как можно большего). Соответственно, для разных целей - разные алгоритмы. И довольно интересные. Элементарные (не значит, что простые, значит - не требующие введения сложных понятий и аппаратов) Если не лень - поищите Добавлено через 6 минут Сообщение от Whost Можно даже в 210K + 1, + 11, + 13 ...(всего 48) и даже в 2310k (всего 480) и так до бесконечности и это не случайность. Можно. Но без толку. Хороший результат дает именно 30. Это оптимум. Добавлено через 11 часов 32 минуты Whost, Последовательность 1, 5, 7, 11... (2 перемешанные арифметические) задается формулой a_n = 3n + (3 - (-1)ⁿ)/2 Добавлено через 2 минуты* Выводится это из рекурентного воотношения a_n+2 - a_n = 6 с начальными условиями a₀ = 1, a₁ = 5 Добавлено через 9 минут Если следовать этой методике, для 30 (отсутствие делимых на 2, 3, 5) рекурентное соотношение будет выглядеть так a_n+8 - a_n = 30, а начальных условий будет аж 8. Характеристическое уравнение q⁸ - 1 = 0 имеет 8 комплексных корней. Чтобы найти решение, придется изрядно попотеть, хотя там все линейно. Дальше - хуже. Однако программно решить эту задачу не должно быть принципиально сложно. Правда, кое-какие сведения из математики лишними не будут 2

@Whost 30 / 30 / 22 Регистрация: 13.02.2016 Сообщений: 131
	13.05.2016, 13:34 [ТС]	8
	Почему же без толку? Для 210 мы должны найти 1 и 47 первых простых чисел начиная с 11, получится 48 последовательностей, которые по сути можно впихнуть в 24(делать последовательности вида 210k +- a), что даст еще примерно 4% прирост производительности. Дальше уже да, смысла почти нет, но по идее некоторый прирост(1-2%) это еще будет давать(до числа 19, дальше уже еле дотягивает до 0.5%). Но я спрашивал немного другое, попробую еще раз объяснить: Мы имеем последовательность 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49 ... Число 5 стоит на позиции 1, число 25 (5^2) на позиции 8. Так вот, мне нужно придумать формулу, в которую я могу подставить 1 и получить 8 и так для каждого числа, то есть для 7, который находится на позиции 2, я должен получить 16, то есть позицию числа 49. Проблема в том, что я понятия не имею, как составлять такие формулы, разве что методом подбора. 0

Байт Диссидент 27495 / 17183 / 3784 Регистрация: 24.12.2010 Сообщений: 38,704
	13.05.2016, 15:05	9
	Сообщение было отмечено Whost как решение Решение Сообщение от Whost Проблема в том, что я понятия не имею, как составлять такие формулы, Я уже привел в посте 7 такую формулу Сообщение от Байт Whost, Последовательность 1, 5, 7, 11... (2 перемешанные арифметические) задается формулой an = 3*n + (3 - (-1)n)/2 и метод ее получения через рекурентные уравнения с начальными условиями. Точнее, это формула общего члена исходной последовательности 1, 5, 7, 11... Но из нее несложно получить и формулу для номера квадрата a_n² = a_k. Считаешь n известным и ищешь k. Там могут возникнуть некоторые сложности с членом (-1)^k, но я думаю, они легко обходятся. Рассмотри несколько примеров и поймай закономерность. Для начала k надо считать приближенно с точностью до 1/6. А потом прибавить - отнять эту 1/6. Я думаю, ее знак получится автоматом при округлении k до ближайшего целого. 1

@Whost 30 / 30 / 22 Регистрация: 13.02.2016 Сообщений: 131
	13.05.2016, 16:42 [ТС]	10
	Байт, спасибо, получилось! С (-1)^k не было проблем(k всегда четный, поэтому просто представил как 1) Правда есть одна проблема: в конечной формуле - $https://www.cyberforum.ru/cgi-bin/latex.cgi?3n^2 + 1/2 + 3n - n(-1)^n$ есть 1/2 так что нужно либо делать две формулы: $https://www.cyberforum.ru/cgi-bin/latex.cgi?3n^2 + 1 + 3n - n(-1)^n$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?3n^2 + 3n - n(-1)^n$ , либо переделывать эту. У меня получилось так $https://www.cyberforum.ru/cgi-bin/latex.cgi?3n ^ 2 + 1/2 - (-1) ^ n/2 + 3n - n( - 1) ^ n$ , но может есть способ сделать лучше? 0

Опции темы

Байт Диссидент 27495 / 17183 / 3784 Регистрация: 24.12.2010 Сообщений: 38,704
	13.05.2016, 22:47	11
	Сообщение от Whost С (-1)^k не было проблем(k всегда четный, поэтому просто представил как 1) А и правда! Чего-то мне в голову не пришло... Сообщение от Whost В математике я полный ноль, Скорее всего это скромность и немножко кокетства (и то и другое - вполне простительно) Математические Нули как правило даже не задумываются об таких штуках. Увы! я тоже в этом деле отнюдь не мажор, просто чего-то нахватался, и что-то было интересно. А простые числа, да, они завораживают. Вроде все так просто, на уровне арифметики 5-го класса. Но чем ближе к бесконечности (хороший пассаж - посмейтесь вместе со мной) тем все становится интересней. Удачи вам, и не скучать! 0

@Whost 30 / 30 / 22 Регистрация: 13.02.2016 Сообщений: 131
	14.05.2016, 08:28 [ТС]	12
	Сообщение от Байт Скорее всего это скромность и немножко кокетства (и то и другое - вполне простительно) Считаю себя нулем, т.к. дальше школьной программы не ушел, а когда смотрю некоторые формулы и математические объяснения по тем же простым числам, то кроме случайного набора букв и цифр ничего не вижу. Сообщение от Байт Удачи вам, и не скучать! Спасибо, удача мне сейчас очень пригодится, чтобы разобраться в этих линейных рекуррентных последовательностях. Кстати новый алгоритм по вашей формуле дал почти двухкратный прирост скорости, по сравнению с алгоритмом с только нечетными числами. Правда я не учитывал преобразование позиций в нормальные простые числа, но все равно впечатляет. 0