Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Оптимальная линейка для последовательностей OEIS
СообщениеДобавлено: 13 авг 2018, 16:45 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 1011
Cпасибо сказано: 32
Спасибо получено:
121 раз в 116 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
Все знакомы с творением Д.Кнута - сайтом целочисленных последовательностей https://oeis.org
Пусть мы хотим получить первые члены знакоположительной последовательности с помощью линейки с минимальным количеством делений.
Первое деление [math]0[/math], остальные надо получить. Замеряя расстояние между любыми двумя делениями, мы можем получить на линейке с [math]n[/math] делениями [math]qR=\frac{n \cdot (n-1)}{ 2 }[/math] первых членов.
Пример: натуральный ряд:

[math]n=3[/math] линейка с делениями [math]p=(0, 1, 3)[/math]: [math](1=1-0; 2=3-1; 3=3-0)[/math] - абсолютное приближение чисел от 1 до 3. Пойдёт, конечно, и [math]p=(0, 2, 3)[/math]
[math]n=4[/math] линейка с делениями [math]p=(0, 1, 4, 6)[/math] - абсолютное приближение чисел от 0 до 6.
Дальше точного соответствия не получается: число делений растёт арифметически, а желающих получиться членов последовательности - квадратично. Потому примем самый "аналитический" критерий оптимальности - [math]\Delta S=min(\sum\limits_{0}^{qR-1}(p_i-a_i )^2)[/math], где [math]a_i[/math] - приближаемая последовательность.
qP\Delta S
530167.810.2
614016.33331113.515.16667
72301.714296.714299.1428617.2857120.5712921.571429
88601.253.1251117.2522.87525.7529.75

Как получать оптимальные решения для больших qP? - А большое начинается уже где-то в районе [math]qP>20[/math] - проклятие размерности, ничего мистического. Так если мы возьмём для перебора по 5 значений для каждого [math]p_i[/math], получим [math]5^{20}=9.537e13[/math] вычислений функции.
Ну и смотрим на саму функцию. Прежде всего, это классическая много-много-fiele-many-багато-molto-экстремальная функция. К тому же с разрывной производной.
К счастью, выбранный нами КО [math]\Delta S[/math] допускает эффективную итерацию. Большинство последовательностей приближаются ею за пару сотен шагов с точностью только порядка процента отличающуюся от оптимального значения. Дальнейшие приближения идут по типу: делаем большой случайный шаг - и ищем итерациями оптимум в данном районе. Нашли, сравнили старый и новый - если новый лучше, переехали в него.

Функция что называется реально вычислимая. Я считал приближение для такой неудобной последовательности как простые числа. Приближение вполне удовлетворительное.

Программа считает на PascalABC, но интересующиеся могут перевести её на любой иной язык.

Отсюда вытекает целый ряд задач.
1. Самая увлекательная из них: найти такую последовательность из OEIS для приближения, что приближающая последовательность, укрупнённая до целых путём [math]p_i=qP \cdot p_i[/math] - получатся именно целые числа - сама вдруг обнаружится в OEIS - по совсем другому поводу. конечно.
2. Найти самую плохо приближающуюся последовательность - задача имеет смысл, подумайте.
3. Получить аналитические функции, приближающие последовательности [math]p_i[/math] для известных последовательностей при их [math]{a_i \stackrel{ f }{\to} + \infty }[/math]
4. Использовать "трудные" последовательности из OEIS для отработки и тестирования программ и алгоритмов поиска глобального экстремума.

Последняя задача имеет широкое практическое значение.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальная линейка для последовательностей OEIS
СообщениеДобавлено: 13 авг 2018, 19:48 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Я понял примерно 10% текста. Но возможно вы ищете это

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальная линейка для последовательностей OEIS
СообщениеДобавлено: 13 авг 2018, 19:51 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Я понял примерно 10% текста. Как ваши соображения соотносятся с этим?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальная линейка для последовательностей OEIS
СообщениеДобавлено: 13 авг 2018, 20:59 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 1011
Cпасибо сказано: 32
Спасибо получено:
121 раз в 116 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
swan
Отличия от линейки Голомба (ЛГ):
1. Деления линейки целые, моя последовательность [math]p_i[/math] в общем случае действительная.
2. ЛГ абсолютно точно аппроксимирует сколько возможно первые члены натурального ряда. [math]p_i[/math] допускает отклонения от ряда и без потерь аппроксимирует все возможные [math]qP \cdot (qP-1)[/math] членов.
3. ЛГ аппроксимирует только натуральный ряд. Мой алгоритм решает любую положительную последовательность.
4. Я за час смогу переделать программу, чтоб она считала ЛГ. А чтоб она считала хорошо, мне нужна неделя.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальная линейка для последовательностей OEIS
СообщениеДобавлено: 13 авг 2018, 21:22 
Не в сети
Оракул
Зарегистрирован:
13 дек 2015, 17:51
Сообщений: 952
Cпасибо сказано: 154
Спасибо получено:
150 раз в 135 сообщениях
Очков репутации: 11

Добавить очки репутацииУменьшить очки репутации
atlakatl
Пока нет программы, можно привести в качестве примера аппроксимацию простых чисел

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальная линейка для последовательностей OEIS
СообщениеДобавлено: 13 авг 2018, 21:56 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 1011
Cпасибо сказано: 32
Спасибо получено:
121 раз в 116 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
bimol
Программу я мог бы выложить, подскажите только куда.
А аппроксимация вот она:
[math]qP=3, dS=0
0 2 5

qP=4, dS=0.5
0 7.5 10.75 12.75

qP=5, dS=1.4
0 7.2 10.6 12.6 29.6

qP=6, dS=13.3333333333333
0 16.6666666666667 35.3333333333333 40.6666666666667 44.8333333333333 47.5

qP=7, dS=27.7142857142857
0 8 14.5714285714286 27.5714285714286 31 69.1428571428571 73.7142857142857

qP=8, dS=57.25
0 6.375 9.875 13.75 42.75 68.5 88.5 109.25

qP=9, dS=154.777777777778
0 6.88888888888889 15.1111111111111 31.5555555555556 36.8888888888889 84.8888888888889 103.111111111111 143.444444444444 146.111111111111

qP=10, dS=243.2
0 4.4 46.1 70.7 105.9 156.5 169.3 178.7 185.7 196.7

qP=11, dS=284.363636363636
0 17.0909090909091 60.1818181818182 70 116.363636363636 153.454545454545 221.363636363636 226.818181818182 242 250.181818181818 256.545454545455

qP=12, dS=427.833333333333
0 4.41666666666667 7.91666666666667 14 43 111.5 174.666666666667 194.166666666667 240 265.333333333333 288.5 319.5

qP=13, dS=651.923076923076
0 13.2307692307692 39.6923076923077 54 77.2307692307692 112 235.076923076923 252.153846153846 282.307692307692 303.538461538462 385.769230769231 390.230769230769 396.769230769231

qP=14, dS=1399.71428571429
0 7.85714285714286 15.9285714285714 28.2142857142857 37.3571428571429 110.785714285714 195.928571428571 256.5 298.071428571429 345.214285714286 394.785714285714 419.5 462.642857142857 473.214285714286

qP=15, dS=3508.66666666666
0 8 36 60.1333333333333 69.6 100.533333333333 262.266666666667 278.666666666667 346.4 434.133333333333 448 454.266666666667 530.933333333333 574.866666666667 580.2

qP=16, dS=7225.375
0 9.625 21.125 93.75 149.375 164 253.875 270.625 367.875 445.25 579.875 602.25 625.6875 632.0625 661 668.625

qP=17, dS=16912.5294117647
0 11.9411764705882 19.3529411764706 58.3529411764706 91.1764705882353 214.588235294118 269.058823529412 277.764705882353 313.176470588235 450.470588235294 616.588235294118 640.470588235294 666.470588235294 682.705882352941 756.470588235294 770.941176470588 784.470588235294

qP=18, dS=30978
0 8.44444444444444 16.4444444444444 39 53.4444444444444 65.5555555555556 207.777777777778 318.333333333333 423.333333333333 495.222222222222 572.777777777778 657.833333333333 661.722222222222 753.444444444444 785.444444444444 844.111111111111 885.777777777778 906.333333333333

qP=19, dS=51354.3157894737
0 16.9473684210526 37.0526315789474 117.263157894737 135.947368421053 144.789473684211 208.526315789474 286.315789473684 439.157894736842 600.210526315789 640.842105263158 693.052631578947 764.631578947368 797.473684210526 974.947368421053 984.947368421053 1017.05263157895 1031.15789473684 1041.68421052632

qP=20, dS=93345.5
0 17.85 25.95 34.7 44.5 173 233.4 263.9 358.1 610.7 634.1 688.2 768.8 892.5 994.8 1057 1069.4 1106.2 1158.4 1173.5[/math]


Так ряд [math](0, 2, 5)[/math] строит [math]2=2-0; 3=5-2; 5=5-0[/math] - абсолютно точно первые три простых.

Дальше только приближённо, но всё равно оптимально:
[math]0; 7.5; 10.75; 12.75[/math] строит [math]2=12.75-10.75; 3 \approx 10.75-7.5; 5 \approx 12.75-7.5; 7 \approx 7.5; 11 \approx 10.75; 13 \approx 12.75[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальная линейка для последовательностей OEIS
СообщениеДобавлено: 15 авг 2018, 08:53 
Не в сети
Оракул
Зарегистрирован:
13 дек 2015, 17:51
Сообщений: 952
Cпасибо сказано: 154
Спасибо получено:
150 раз в 135 сообщениях
Очков репутации: 11

Добавить очки репутацииУменьшить очки репутации
А если взять такое приближение 0.5, 8, 11, 13 ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Оптимальная линейка для последовательностей OEIS
СообщениеДобавлено: 15 авг 2018, 10:34 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
09 авг 2018, 23:20
Сообщений: 1011
Cпасибо сказано: 32
Спасибо получено:
121 раз в 116 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
У линейки всегда должен быть 0. Вы фактически имеете его ввиду при формировании простых 11 и 13 - когда на самом деле следует отнять из них Ваш член 0.5. И тогда невязка становится больше оптимальной: 0.75.
Интуиция на таких функциях не работает. Попробуйте, не заглядывая в ответ, расставить 10 точек оптимальным образом. - Приближает первые 45 простых.
[math]0, 16.2, 39, 73.4, 100, 143.2, 178.4, 185.1, 189.1, 196.6[/math]
Невязка [math]sMin=243.2[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю atlakatl "Спасибо" сказали:
bimol
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 8 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Перевод и разбор статей из OEIS

в форуме Размышления по поводу и без

ivashenko

21

1100

28 ноя 2015, 15:22

Проверка принадлежности числа к OEIS.A146085

в форуме Ряды

YarRainbow

1

206

09 авг 2021, 17:56

Оптимальная выплавка

в форуме Исследование операций и Задачи оптимизации

grumpy

0

309

01 июн 2015, 04:24

Оптимальная оценка

в форуме Математическая статистика и Эконометрика

Stasya7

0

535

29 ноя 2015, 16:47

Оптимальная длинна дорожки?

в форуме Алгебра

lefosaj871

4

149

27 апр 2021, 18:12

Оптимальная фильтрация (фильтры Калмана)

в форуме Теория вероятностей

n1733

0

266

25 май 2016, 22:49

Оптимальная стратегия и теория вероятности

в форуме Комбинаторика и Теория вероятностей

YTigiev

2

204

18 дек 2020, 11:22

Оптимальная конфигурация зарядов в шаре

в форуме Исследование операций и Задачи оптимизации

searcher

2

227

12 окт 2021, 12:02

Лимиты Последовательностей

в форуме Пределы числовых последовательностей и функций, Исследования функций

roket177

1

263

31 окт 2014, 21:47

Предел последовательностей

в форуме Пределы числовых последовательностей и функций, Исследования функций

Kosta

2

312

28 ноя 2015, 00:03


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved