О некоторых свойствах и оценках для последовательностей простых чисел

Розглянуто спеціальні послідовності простих чисел, їх властивості, введено операції на розглянутих послідовностях, отримано оцінки для інтервалів розміщення найближчих до заданого числа простих чисел. Запропоновано алгоритм для наближення довільного раціонального числа за допомогою елементів введени...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2015
Hauptverfasser:	Ивохин, Е.В., Ваднев, Д.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы управления и оценивания в условиях неопределенности
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/208050
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	О некоторых свойствах и оценках для последовательностей простых чисел / E.В. Ивохин, Д.А. Ваднев // Проблемы управления и информатики. — 2015. — № 6. — С. 105-118. — Бібліогр.: 6 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208050
record_format	dspace
spelling	irk-123456789-2080502025-10-19T00:03:16Z О некоторых свойствах и оценках для последовательностей простых чисел Про деякі властивості та оцінки для послідовностей простих чисел On the properties and estimates for the prime numbers sequences Ивохин, Е.В. Ваднев, Д.А. Методы управления и оценивания в условиях неопределенности Розглянуто спеціальні послідовності простих чисел, їх властивості, введено операції на розглянутих послідовностях, отримано оцінки для інтервалів розміщення найближчих до заданого числа простих чисел. Запропоновано алгоритм для наближення довільного раціонального числа за допомогою елементів введених послідовностей простих чисел. Доведено твердження для оцінок інтервалів розміщення найближчих до заданого цілого простих чисел. Отримані результати дозволяють обгрунтувати методику побудови трикутних нечітких чисел у вигляді інтервалів, границі яких обираються за допомогою елементів спеціальних послідовностей простих чисел. The specific sequences of prime numbers, their properties, operations introduced on these sequences are considered. The estimates for arrangement intervals of the prime numbers the closest to the specified number are obtained. An algorithm to approximate an arbitrary rational number using elements of introduced sequences of primes is proposed. The statement for estimates of arrangement intervals of the closest to specified integer prime numbers. are proved. The obtained results enable us to substantiate the method of constructing triangular fuzzy numbers in the form of intervals the boundaries of which are selected using the members ofspecial sequences of prime numbers. 2015 Article О некоторых свойствах и оценках для последовательностей простых чисел / E.В. Ивохин, Д.А. Ваднев // Проблемы управления и информатики. — 2015. — № 6. — С. 105-118. — Бібліогр.: 6 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208050 519.87 10.1615/JAutomatInfScien.v47.i12.40 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы управления и оценивания в условиях неопределенности Методы управления и оценивания в условиях неопределенности
spellingShingle	Методы управления и оценивания в условиях неопределенности Методы управления и оценивания в условиях неопределенности Ивохин, Е.В. Ваднев, Д.А. О некоторых свойствах и оценках для последовательностей простых чисел Проблемы управления и информатики
description	Розглянуто спеціальні послідовності простих чисел, їх властивості, введено операції на розглянутих послідовностях, отримано оцінки для інтервалів розміщення найближчих до заданого числа простих чисел. Запропоновано алгоритм для наближення довільного раціонального числа за допомогою елементів введених послідовностей простих чисел. Доведено твердження для оцінок інтервалів розміщення найближчих до заданого цілого простих чисел. Отримані результати дозволяють обгрунтувати методику побудови трикутних нечітких чисел у вигляді інтервалів, границі яких обираються за допомогою елементів спеціальних послідовностей простих чисел.
format	Article
author	Ивохин, Е.В. Ваднев, Д.А.
author_facet	Ивохин, Е.В. Ваднев, Д.А.
author_sort	Ивохин, Е.В.
title	О некоторых свойствах и оценках для последовательностей простых чисел
title_short	О некоторых свойствах и оценках для последовательностей простых чисел
title_full	О некоторых свойствах и оценках для последовательностей простых чисел
title_fullStr	О некоторых свойствах и оценках для последовательностей простых чисел
title_full_unstemmed	О некоторых свойствах и оценках для последовательностей простых чисел
title_sort	о некоторых свойствах и оценках для последовательностей простых чисел
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2015
topic_facet	Методы управления и оценивания в условиях неопределенности
url	https://nasplib.isofts.kiev.ua/handle/123456789/208050
citation_txt	О некоторых свойствах и оценках для последовательностей простых чисел / E.В. Ивохин, Д.А. Ваднев // Проблемы управления и информатики. — 2015. — № 6. — С. 105-118. — Бібліогр.: 6 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT ivohinev onekotoryhsvojstvahiocenkahdlâposledovatelʹnostejprostyhčisel AT vadnevda onekotoryhsvojstvahiocenkahdlâposledovatelʹnostejprostyhčisel AT ivohinev prodeâkívlastivostítaocínkidlâposlídovnostejprostihčisel AT vadnevda prodeâkívlastivostítaocínkidlâposlídovnostejprostihčisel AT ivohinev onthepropertiesandestimatesfortheprimenumberssequences AT vadnevda onthepropertiesandestimatesfortheprimenumberssequences
first_indexed	2025-10-19T01:09:55Z
last_indexed	2025-10-20T01:13:02Z
_version_	1846461367262904320
fulltext	© Е.В. ИВОХИН, Д.А. ВАДНЕВ, 2015 Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 6 105 УДК 519.87 E.В. Ивохин, Д.А. Ваднев О НЕКОТОРЫХ СВОЙСТВАХ И ОЦЕНКАХ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРОСТЫХ ЧИСЕЛ Введение В истории науки есть по крайней мере одна глава, связывающая воедино труды величайших ученых со времен античности и до наших дней. Глава эта по- священа простым числам — атомам арифметики. Казалось бы, за безобидным на- званием этих чисел, которые делятся только на единицу и на самих себя, скрыва- ется одна из сложнейших проблем, когда-либо возникавших перед исследовате- лями-математиками [1]. Со времен Евклида математики пытаются разглядеть некоторую законо- мерность в распределении простых чисел на числовой оси. Если посмотреть даже на наименьшие простые числа, то вряд ли можно усмотреть какую -либо логику в их расположении на числовой оси. И такая логика становится все более и более эфемерной по мере того, как мы продолжаем углубляться в чи- словые дебри. Развитие теории простых чисел в некотором смысле отражает эволюцию методов математического познания: от выдвижения эмпирических (интуи- тивных) гипотез и такой же эмпирической их проверки до предоставления доказательного обоснования, возводящего утверждения в ранг теорем. Прин- цип логически обоснованного доказательства утверждений, впервые откры- тый в древней Греции, позволяет перейти из области человеческой интуиции в пространство истинного, объективного знания, отражающего устройство природы. Чтобы продвинуться в понимании простых чисел, потребовались многие годы и математическое чутье величайших математиков истории. Один из них — Карл Гаусс, который, изучая таблицы простых чисел в книге с лога- рифмами, сумел разглядеть закономерность в расположении этих необычных чисел на числовой оси. Гениальность его догадки заключается в том, чтобы не предсказывать, является ли произвольное натуральное число N простым, а оценить, сколько в среднем простых чисел находится на заданном отрезке. Слово «оценить» в данной постановке вопроса принципиально, поскольку знание истинного количества простых чисел на отрезке [2, K], которое обо- значают как ),(K позволяет точно сказать, является ли произвольное целое число N простым. Именно точная зависимость ),(K имеющая вид ступенча- той функции, всегда служила заветной целью для математиков. И оценочный подход Гаусса дал первое существенное приближение к этой зависимости. Рассмотрим альтернативные способы оценивания и использования про- стых чисел. 1. Специальные последовательности простых чисел и их свойства Последовательности простых чисел можно эффективно использовать при решении многих прикладных задач с применением вычислительных схем [2]. Введем отдельные понятия и операции. 106 ISSN 0572-2691 Определение 1. Последовательности неотрицательных простых чисел ,0)( aPj ,Zj принадлежащих интервалу ),[ a при 0j или интервалу ),0[ a при 0j для заданного, необязательно простого, целого числа ,0a будем называть последовательностями простых чисел относительно числа .a Пусть заданы простые числа 0)( aPj с порядковыми номерами Zj из последовательности простых чисел относительно числа .0a Нетрудно прове- рить, что справедливы соотношения, характеризующие свойства последователь- ности простых чисел: 1) ,0)0(0 P ,1)1(0 P ;1)0(1 P 2) ,)(0 aaP  если число 0a простое, иначе )(0 aP не существует; 3) ),()( aPaP kj  если ,kj  )()( aPaP kj  при ,kj  ,Zj ;Zk 4) )(...)1()( laPaPaP jjj  для всех ),()(1 1 aPaPl jj   ,...,2,1,0j ;0a 5) )),((...))(()))((())(()( 112221111 aPPaPPaPPPaPPaP jjjjj   если число 0a простое, ;Zj 6) aaPj )( для всех ,...,2,1,0j если число 0a простое, aaPj )( для всех ,...,2,1j если 0a непростое; 7) aaPj )( для всех ,...,,2,1 0jj  где номер 00 j определяется как наименьший индекс простого числа из последовательности, для которого .)(0 0 aaPj  Если 0a — простое число, то существует число ).(0 aP Используя ука- занные выше свойства, получаем соотношения  )(/)(,1)(/)( aPaPaPaP kjkj ))((/)())((/)(...))((/)( 11 aPPaPaPPaPaPPaP jjkjjkjjkj   для любых ,, Zkj  .kj  Кроме традиционных арифметических операций сложения, вычитания, ум- ножения и деления простых чисел, для последовательностей простых чисел ),(aPj ,...,2,1,0j относительно произвольного 0a введем операцию смеще- ния на ,m ,Zm ,0jmj  простых чисел в виде )),(()()( aPPaPmaP jmmjj   (1) которая по определению не выводит за нижнюю границу заданной последова- тельности ),( 0jmj  и операцию n -кратной композиции )( Zn отношения двух чисел: )(aPj и ),(aPk ,, Zkj  ,kj  в виде )).((/))(()(/)()(/)()(/)( aPPaPPaPaPnaPnaPnaPaP knjnnknjkjkj   (2) Предположим, что рассматривается произвольное рациональное число r. Без ограничения общности, будем считать, что число r неотрицательное, .0r Лемма 1. Произвольное рациональное число ,/ qpr  ,Zp ,Nq может быть представлено в виде ,)()( 11 /   q jj p ii s j nn s i kk aPaPr (3) где qp ss , — число сомножителей в представлении p и q в виде соответствую- щих произведений элементарных делителей, ,0 ika 0 jna — некоторые целые числа, ,, Znk ji  ,,1 psi  .,1 qsj  Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 6 107 Доказательство. Известно, что произвольное рациональное число r пред- ставляется в виде простой дроби ,/ qpr  ,Zp .Nq Если при этом оба числа (p и q ) являются простыми числами, то получаем утверждение леммы. В данном случае ,1,1  qp ss ,)( 11 paP kk  qaP nn )( 11 для некоторых ,1 Zk  Zn 1 и ,0 1 ka .0 1 na Если числитель или знаменатель или оба числа ( p и q ) не являются про- стыми, то их можно представить в виде произведения элементарных делителей, являющихся простыми числами. Количество записей элементарных делителей в произведениях соответствует их кратности. Обозначим количество сомножителей в представлении чисел p и q в виде соответствующих произведений через ,, qp ss где каждый из сомножителей является простым числом из некоторых по- следовательностей простых чисел относительно чисел , ika , jna ,, Znk ji  ,,1 psi  .,1 qsj  Представление (3) для произвольного рационального числа r доказано. Следствие 1. Произвольное рациональное число ,/ qpr  ,Zp ,Nq мо- жет быть представлено в виде ),()( 11 / aPaPr j q i p n s j k s i    (4) где qp ss , — число сомножителей в представлении p и q в виде соответствующих произведений элементарных делителей, 0a — некоторое целое число, ,Zki  ,Zn j  ,,1 psi  .,1 qsj  Следствие 2. Произвольное рациональное число ,/ qpr  ,Zp ,Nq мо- жет быть представлено в виде ),0()0( 11 / ji n s j k s i PPr    (4) где s — максимальное значение сомножителей в представлении чисел p и q в ви- де соответствующих произведений элементарных делителей, },0{, Nnk ji ,,1 psi  .,1 qsj  Лемма 2. Для произвольного рационального числа r и заданного Nn су- ществуют целые числа ,0a 0b и простые числа с номерами Zi * и Zj * из последовательностей простых чисел относительно a и b соответственно, та- кие, что для всех ,, Nji  ,ni  ,nj  справедливо неравенство .)()()()( ** rbPaPrbPaP jiji  (5) Доказательство. Рассмотрим возрастающую последовательность всех про- стых чисел ,0ip ,Ni причем 0 и 1 также считаем простыми числами. Пред- положим, что задано рациональное число r и целое .Nn 108 ISSN 0572-2691 Покажем существование простых чисел с номерами ,Nio  ,Njo  для которых выполняется соотношение rpprpp jiji oo  для всех ,, Nji  ,ni  ,nj  на основе следующего алгоритма. 0. Положим ,0i .1j 1. Пока ni  и ,nj  повторяем пп. 2– 4. 2. Если ,rpp ji  то решение найдено, ,iio  .jjo  Переходим к п. 5. 3. Если ,rpp ji  то увеличиваем номер 1 ii и вычисляем новое простое число ;0ip в противном случае увеличиваем номер 1 jj и находим простое число .0jp 4. Если ,rpprpp oo jiji  то фиксируем ,iio  .jjo  5. Значения ,oi oj — решение поставленной задачи. Очевидно, что соответствующие простые числа oo ji pp , могут рассматри- ваться в качестве элементов последовательностей простых чисел относительно некоторых ,0a 0b с номерами Zi * и Zj * соответственно. Далее покажем, что значения ,i ,j найденные с помощью описанного вы- ше алгоритма, являются оптимальным решением задачи. Пусть, от противного, существуют значения ,, 00 Nji  ,0 ni  ,0 nj  такие, что для соответствующих элементов из последовательности простых чисел спра- ведливо . 00 rpprpp oo jiji  Так как значения номеров i и j в алгорит- ме монотонно увеличиваются, то существует значение ,Ni  ,ni  такое, что на некоторой итерации алгоритма имеем ,ii  .0jj  Аналогично существует зна- чение ,Nj  ,nj  такое, что на некоторой итерации алгоритма ,0ii  .jj  При этом либо ,0ii  либо 0jj  (иначе алгоритм проходил бы через значения ,ii  0jj  и ,0ii  ,jj  для которых 0ii  и ).0jj  Без ограничения общности рассмотрим случай .0ii  Пусть ,min Ni  oii min — наименьшее значение номера i такое, что . 0 min rpp ji  Если ,0 min ii  то на определенном шаге алгоритм проходит через значения номеров ., 00 jjii  Тогда имеем , 00 rpprpp oo jiji  что противоре- чит предположению. Таким образом, ,0 min ii  и, как следствие, . 000 min jiji pppp  . 000 min jiji pppp  Из данных соотношений имеем , 000 min rpprpprpp jijiji oo  что снова противоречит предположению. Окончательно можно сделать вывод, что не существует номеров ,, 00 Nji  ,0 ni  ,0 nj  таких, что . 00 rpprpp oo jiji  Лемма доказана. Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 6 109 Следствие 1. Для произвольного рационального числа r и заданного Nn существуют простые числа с номерами Ni * и Nj * из последовательности простых чисел относительно числа 0a такие, что для всех ,, Nji  ,ni  ,nj  справедливо неравенство .)0()0()0()0( ** rPPrPP jiji  (5) Доказательство. Нетрудно заметить, что если положить ,0 ba то, повто- ряя доказательство леммы, получаем справедливость соотношения (5). Лемма 3. Для произвольных двух простых чисел: ),(aPk ),(aPn ,nk  ,, Znk  из последовательности простых чисел относительно числа a и произ- вольного числа 0T справедливо соотношение .)()())(())(( aPaPTaPTaP nknk  (6) Доказательство. Несложно проверить, что для любых ,nk  ,, Znk  име- ет место .))())((())()(()()())(())(( aPTaPaPaPTaPaPTaPTaP nnknnknk  Учитывая свойство 3) последовательностей простых чисел, получаем, что ,0)()())(())((  aPaPTaPTaP nknk откуда следует неравенство (6). Лемма доказана. Рассмотрим множество неотрицательных рациональных чисел ),,( nkr ,, Znk  ,1),(0  nkr которые представляются в виде отношения двух простых чисел из последовательности относительно числа :0a ,)()(),( aPaPnkr nk ,nk  ., Znk  (7) Без ограничения общности положим .0a При этом рациональные числа ),( nkr будут представляться в виде ),0()0(),( nk PPnkr  ,nk  }.0{, Nnk (8) С учетом операции смещения на m простых чисел в последовательности ),0(jP Zj получаем соотношения ,),(),( mnkrmnmkr  }.0{Nm (9) Введем в рассмотрение другие числовые совокупности. Определение 2. Множество рациональных чисел ),,( nkrT ,0T ,nk  },0{, Nnk вида ),)0(())0((),( TPTPnkr nkT  ,nk  },0{, Nnk (10) назовем T-последовательностью для множества чисел ),( nkr и заданного .0T Определение 3. Для заданного множества чисел ),,( nkr ,nk  },0{, Nnk множество чисел , )0( )0( ),( * mP mP mnmkr n k    ,nk  ,Zm },0{, Nnk (11) 110 ISSN 0572-2691 где * m : mm  * 0 при },0{Nm и mm  * при ,0m — наибольшее целое число такое, что ,)0(/)0()0(/)0( * mPmPmPmP nknk  будем называть нижним сопряженным множеством, а множество чисел , )0( )0( ),( * * mP mP mnmkr n k    ,nk  ,Zm },0{, Nnk (12) где :m mm  при }0{Nm и 0*  mm при ,0m — наименьшее целое число такое, что ,)0(/)0()0(/)0( * mPmPmPmP nknk  — верхним сопряженным множеством. Лемма 4. Справедливы следующие соотношения: ),,(),( nkrnkr T (13) ),,(),(* mnmkrmnmkr  (14) ),,(),( * mnmkrmnmkr  (15) ),(),(* mnmkrmnmkr T  (16) для произвольных ,0T },0{, Nnk ,nk  .Zm Доказательство. В соответствии с леммой 3 для произвольного числа 0T справедливо неравенство ),()0()0())0(())0((),( nkrPPTPTPnkr nknkT  и выполняются соотношения ),,( )0( )0( )0( )0( ),( * * mnmkr mP mP mP mP mnmkr n k n k        ),( )0( )0( )0( )0( ),( * * mnmkr mP mP mP mP mnmkr n k n k        для произвольных значений },0{, Nnk nk  и любого .Zm Таким обра- зом, неравенства (13)–(15) доказаны. Неравенство (13) выполняется для всех },0{, Nnk .nk  Тогда для лю- бого Zm имеем ,mnmk  откуда для любого 0T справедливо соотно- шение ).,(),( mnmkrmnmkr T  С учетом неравенства (14) окончательно получаем ),,(),( * mnmkrmnmkr T  что соответствует неравенству (16). Следствие 1. Для произвольных значений ,0T  ,0Nk  ,0Nn nk  справедливы соотношения ),,(),( * nkrnkr  (17) ),,(),( * nkrnkr  (18) ).,(),( * nkrnkr T (19) Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 6 111 Доказательство. Справедливость неравенств (17)–(19) очевидна. Действи- тельно, положим 0m в соотношениях (14)–(16). В результате получаем нера- венства (17)–(19) для произвольных значений ,0T  ,0Nk  ,0Nn ,nk  что и требовалось доказать. Очевидно, что свойство элементов совокупности ),( nkr в виде 1),(0  nkr сохраняется для всех членов T -последовательности с произвольным значением 0T и элементов нижнего и верхнего сопряженных множеств: ,1),(0  nkrT ,1),(0 *  mnmkr 1),(0 *  mnmkr (20) для всех },0{Nk },0{Nn ,nk  и любого }.0{Nm Из леммы 4 и следствия можно сделать вывод, что существуют соотношения между соответствующими элементами множеств ),,( nkr },0{Nk },0{Nn ,nk  и элементами T -последовательности с произвольным значением 0T нижнего и верхнего сопряженных множеств. При этом, к сожалению, ничего нельзя сказать о соотношении чисел ),( nkr и ),( mnmkr  для произвольного }.0{Nm 2. Числовые последовательности, построенные на простых числах Рассмотрим две неубывающие числовые последовательности: )},(),1(max{)( nrngng  ,Nn ,0)0( g (21) где ),(nr ,Nn — расстояние между двумя ближайшими к числу Nn про- стыми числами ),(),( 1 nqnq ss  ,Ns такими, что ),(nqn s ),(1 nqn s т.е. );()()( 1 nqnqnr ss   )},(),1(max{)( nlnpnp  ,Nn ,0)0( p (22) где ),()()( 11 nPnPnl  ,Nn )(),( 11 nPnP — предыдущее и следующее про- стые числа относительно числа .Nn Очевидно, что если Nn — простое число с номером Ns из последователь- ности простых чисел, то nnqs )( и ,)()( 1 nnqnr s   .Nn Значения )(nr в этом случае совпадают с элементами числовой последовательности ,)( 1 ss qqsd   ,Ns 1, ss qq — два последовательных простых числа, .Ns Данная последо- вательность, состоящая из величин расстояний между парами последовательных простых чисел, часто используется в исследованиях совокупностей простых чисел [3]. В некоторых случаях рассматривается числовая последовательность )},(),1(max{)( nqnfnf  ,0)0( f где ),(nq ,Nn — расстояние от числа n до ближайшего к нему простого числа, т.е. nqnq s )( для некоторого Ns [4]. Очевидно, что если Nn — простое число, существует Ns такое, что   ))1()())(())(()()()( 1111 nrnrnPnnnPnPnPnl )),1(()1)((...))2()())1()1(  sdnrsdnrnrnrnrnr или, в более общей форме, )()1()( jnrinrnl  для всех ,)(,1 sdi  )1(,1  sdj и некоторого числа .Ns 112 ISSN 0572-2691 Таким образом, окончательно получаем: 1) последовательности ),(ng )(np неубывающие, кусочно-постоянные с ин- тервалами постоянства )),(),([ 1 nqnq ss  ;Ns 2) для всех Nn справедливо )()( nrnl  и, следовательно, ).()( ngnp  При построении оценок для простых чисел рассматривается последователь- ность ),(nB ,Nn ,1)0( B элементами которой являются целые числа, опреде- ляющие количество разрядов в двоичном представлении числа .Nn Отметим, что для чисел ,2kn  ,...,2,1k справедливы соотношения  1)1()( nBnB ,1)(...1)2(  mnBnB ,2...,,2,1 1 km ,...,2,1k и ).0()1( BB  Свойства. Для элементов рассматриваемых последовательностей выполняю- тся следующие соотношения [5]: 1) для всех 5n справедливо неравенство );(1)( npnB  2) для всех Nn справедливо неравенство );(3,2)( nBng  3) для всех 7n справедливо неравенство ).(6/5)( npnB  Лемма 5. Для всех значений ,Nn ,7n таких, что число 12 n не являет- ся простым, справедливо неравенство ).2()(2 npnp  (23) Доказательство. Используем метод математической индукции: 1) ;7n ;6)7( p ,6)14( p );14()7(2 pp  2) пусть неравенство (23) справедливо для всех mn ,7 при условии, что 12 n составное. При mn  имеем )2()(2 mpmp  и число 12 m не является простым. Покажем, что лемма справедлива и для ,1mn т.е. ).22()1(2  mpmp Из определения последовательности ),(np ,Nn запишем  ,)22(),12(max)22(  mlmpmp )}.12(),2(max{)12(  mlmpmp Если выполняется соотношение ),22()12()2(  mpmpmp то, учитывая, что данная последовательность неубывающая, получаем  )(2)1(2 mpmp ).22()2(  mpmp В более сложном случае предположим, что ).22()2(  mpmp Так как числа ,2m 22 m четные и, следовательно, не являются простыми, а число 12 m составное по условию, то получаем ),22()12()2( 111   mPmPmP )22()12()2( 111  mPmPmP и ).22()12()2(  mlmlml Отсюда )2( mp ),22()12(  mpmp что противоречит предположению. Таким образом, окон- чательно получаем неравенство )).1(2()22()2()(2)1(2  mpmpmpmpmp Следствие 1. Для всех значений ,Nn ,7n таких, что число 12 n не яв- ляется простым, справедливы неравенства ),12()(2  npnp (23) ).22()(2  npnp (23) Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 6 113 Доказательство. При условии, что число 12 n является составным, спра- ведливы равенства ).22()12()2(  npnpnp Учитывая неравенство (23), по- лучаем соотношения (23), (23). Замечание. Необходимо отметить, что при замене в соотношениях (23), (23), (23) строгих неравенств на нестрогие можно получить аналогичные соотноше- ния для всех .Nn В качестве примеров приведем неравенства для :7n ;1n ;2)1( p ,2)2( p ;3)3( p ),2()1(2 pp  ),3()1(2 pp  );4()1(2 pp  ;2n ,2)2( p ,3)4( p ;4)5( p ),4()2(2 pp  ),5()2(2 pp  );4()2(2 pp  ;3n ;3)3( p ,4)6( p ;6)7( p ),6()3(2 pp  ),7()3(2 pp  );8()3(2 pp  ;4n ;3)4( p ,6)8( p ;6)9( p ),8()4(2 pp  ),9()4(2 pp  );10()4(2 pp  ;5n ;4)5( p ,6)10( p ;6)11( p ),10()5(2 pp  ),11()5(2 pp  );12()5(2 pp  ;6n ;4)6( p ,6)12( p ;6)13( p ),12()6(2 pp  ),13()6(2 pp  .6)14()6(2  pp Следствие 2. Для всех значений ,Nn ,5n таких, что число 12 n не яв- ляется простым, справедливы неравенства ).2()(2 npnp  (24) ),12()(2  npnp (24) ).22()(2  npnp (24) Доказательство. Проверим справедливость утверждения для .5n Учитывая, что ,4)5( p ,6)10( p ,6)9( p ,6)8( p непосредственной подстановкой в соот- ношения (24), (24), (24) убеждаемся в их истинности. Предположим далее, что спра- ведлива лемма 5, т.е. для всех ,Nm ,7m таких, что число 12 m является состав- ным, справедливы неравенства ),2()(2 mpmp  ),12()(2  mpmp )(2 mp ).22(  mp Положив ,1 nm перепишем полученные соотношения относительно ,Nn .8n Имеем: число 1212212  nnm — составное и справедливы неравенства ),22()1(2  npnp ),12()1(2  npnp ).2()1(2 npnp  Учиты- вая, что последовательность )(np неубывающая, т.е. )()1( npnp  для всех ,Nn получаем соотношения (24), (24), (24). Для 6n и 7n числа 12 n простые и не удовлетворяют условию следствия. Таким образом, окончательно получаем, что при выполнении условий для ,Nn ,5n таких, что число 12 n не является простым, справедливы неравенства (24), (24), (24). Лемма 6. Для всех значений ,Nn ,4n таких, что число 32 n простое, справедливо неравенство ).(232)32(1 npnnP  (25) Доказательство. Применим метод математической индукции. Учитывая очевидное неравенство при ,4n 3)4( p и условии, 1132 n — простое число имеем ),4(23426381713)11(1 pP  и предполагая справедливость соотношения (25) для всех ,Nn ,,4 mn  прове- рим истинность утверждения для .1 mn 114 ISSN 0572-2691 По условиям леммы число 32 m простое, а число 5232  mn может быть простым или составным. Имеем: 1) 52 m не является простым. В этом случае получаем  )52(1 mP ),1(252)(252)(232)32(1  mpmmpmmpmmP отсюда  )52(1 mP ),1(23)1(2)1(252)3)1(2(1  mpmmpmmP что и требовалось получить; 2) 52 m является простым. Положим .1mk Из (25) имеем  )52(1 mP )1(3)1(2)(32)32(1  mpmkpkkP и, следовательно, справедливо утверждение леммы для .1 mn Лемма доказана. Лемма 7. Для всех значений ,Nn ,4n таких, что число 32 n является простым, справедливо неравенство ).(232)32(1 npnnP  (26) Доказательство. Применяя метод математической индукции, при ,4n 3)4( p и условии, что 1132 n — простое число, имеем очевидное неравенство ).4(234263857)11(1 pP  Предположим справедливость соотношения (26) для всех ,Nn .,4 mn  Проверим истинность утверждения для .1 mn По условиям леммы число 32 m простое, а числа ,5232  mn ),(232 mpm  )(252 mpm  нечетные. Получаем  32)52(1 mmP )(232)32(1 mpmmP   и ).(252)32(1 mpmmP  Учитывая, что ),1()(  mpmp окончательно имеем  )52(1 mP ),1(23)1(2  mpm что и требовалось получить. Следовательно, утверждение леммы остается истинным для .1 mn Лемма доказана. Утверждение 1. Пусть для произвольного значения Nn величина .)( pnp  Тогда справедливы неравенства ),2(122 1 nPpn  (27) ).12(322 1   nPpn (28) Доказательство. Воспользуемся методом математической индукции. 1. ;1n ;2)1( p ,1)2(142 1  P ;2)3(342 1  P ;2n ;2)2( p ,3)4(144 1  P ;3)5(344 1  P ;3n ;3)3( p ,5)6(166 1  P ;5)7(366 1  P ;4n ;3)4( p ,7)8(168 1  P ;7)9(368 1  P ;5n ;4)5( p ,7)10(1810 1  P ,7)11(3810 1  P ;6n ;4)6( p ,11)12(1812 1  P ;11)13(3812 1  P ;7n ;6)7( p ,13)14(11214 1  P .13)15(31214 1  P Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 6 115 2. Предположим, что утверждение справедливо для всех .,1 mn  При mn  имеем );2(122 1 mPpm  (27) ).12(322 1   mPpm (28) Покажем, что данное утверждение справедливо и для .1 mn Для этого рассмотрим различные случаи.  .)()1( pmpmp  Оценим величину ).22())1(2( 11   mPmP Имеем .32212)1(2  pmpm С учетом предположения (28) отсюда следует, что ближайшее простое число, не превосходящее ,22 m либо принадлежит интерва- лу )),12(,322[ 1   mPpm либо .12)22(1  mmP Окончательно имеем )),1(2(12)1(2322 1   mPpmpm что подтверждает справедливость неравенства (27).  .ˆ)1( ppmp  В этом случае аналогично, используя соотношение ,3ˆ22322)12(1  pmpmmP получаем оценку для :)22(1  mP ))12(,3ˆ22[))12(,322[)22( 111   mPpmmPpmmP или ,12)22(1  mmP откуда )).1(2(12)1(2322 1   mPpmpm Справедливость неравенства (27) доказана. Рассмотрим далее соотношение (28). Предполагая справедливость (27), (28), оценим величину ).32()1)1(2( 11   mPmP Аналогично предыдущему проанализируем различные случаи.  .)()1( pmpmp  Имеем .52232)1(2  pmpm Из (27) следует гарантированная оценка для ближайшего простого числа, не превышающего :32 m .322)32(1  pmmP Исходя из очевидного соотношения  pm 22 ,5223  pm покажем, что число 322  pm не может быть ближайшим простым. Действительно, предположим, что интервал )32,322(  mpm не содержит простых чисел. Тогда ближайшими простыми числами в этом случае могут быть 322  pm и .32 m Отсюда следует, что расстояние между ними равняется .2 p Из неравенства (26) леммы 7 имеем   32)32()32( 11 mmPmP .232)(2 pmmp  Следовательно, предположение об отсутствии простых чисел на интервале )32,322(  mpm неверно, откуда получаем .522)32(1  pmmP  .ˆ)1( ppmp  Гарантированная оценка для ближайшего простого числа, не превышающего ,32 m будет иметь вид   )32(2)32( 11 mPmmP .3ˆ22322  pmpm Проведя аналогичные рассуждения, получаем, что число 322  pm не может быть ближайшим простым числом, не превышающим .32 m Следовательно, ,5ˆ22522)32(1  pmpmmP что свидетельст- вует о справедливости неравенства (28). Утверждение доказано. 116 ISSN 0572-2691 Утверждение 2. Пусть для произвольного значения Nn величина .)( pnp  Тогда справедливы неравенства ,322)2(1  pnnP (29) .122)12(1  pnnP (30) Доказательство. Вновь воспользуемся методом математической индукции. 1. ;1n ;2)1( p ,3423)2(1 P ;1425)3(1 P ;2n ;2)2( p ,3445)4(1 P ;1447)5(1 P ;3n ;3)3( p ,3667)6(1 P ;16611)7(1 P ;4n ;3)4( p ,36811)8(1 P ;16811)9(1 P ;5n ;4)5( p ,381011)10(1 P ;181013)11(1 P ;6n ;4)6( p ,381213)12(1 P ;181217)13(1 P ;7n ;6)7( p ,3121417)14(1 P .1121417)15(1 P 2. Предположим, что утверждение справедливо для всех .,1 mn  При mn  имеем ,322)2(1  pmmP (29) .122)12(1  pmmP (30) Покажем, что данное утверждение справедливо и для .1 mn Оценим ве- личину ).22())1(2( 11  mPmP Для этого рассмотрим различные случаи.  .)()1( pmpmp  В этом случае 12232)1(2  pmpm и с учетом предположения (30) следует, что ближайшее простое число, превосходящее ,22 m принадлежит интервалу ].122),32([ 1  pmmP Таким образом,  ))1(2(1 mP ,32)1(2122  pmpm что подтверждает справедливость неравенства (29).  .ˆ)1( ppmp  Используя соотношение  122)12(1 pmmP ,1ˆ22  pm в этом случае получаем аналогичную оценку для :)22(1 mP  )22(1 mP ]1ˆ22),12((]122),12(( 11  pmmPpmmP или  ))1(2(1 mP 122))1(2(1  pmmP .32)1(2  pm Справедливость неравенства (29) доказана. Рассмотрим далее соотношение (30). Предполагая справедливость (29), (30), оценим величину ).32()1)1(2( 11  mPmP Аналогично предыдущему проана- лизируем различные случаи.  .)()1( pmpmp  Имеем .12212)1(2  pmpm Из (30) следует гарантированная оценка для ближайшего простого числа, превышающего :32 m .122  pm Если число 32)32(1  mmP не является простым, то  )12(1 mP )32()22( 11  mPmP  122 pm 122  pm и неравенство (30) доказано. Пусть 32 m — простое число. Исходя из очевидного соотношения ,322122122  pmpmpm покажем, что число 322  pm не может быть ближайшим к 32 m простым числом. Международный научно-технический журнал «Проблемы управления и информатики», 2015, № 6 117 Действительно, предположим от противного, что интервал ,32( m )322  pm не содержит простых чисел. Тогда ближайшими простыми числами в этом случае могут быть 32 m и .322  pm Это означает, что расстояние ме- жду ними равняется .2 p Из неравенства (25) леммы 6 имеем  mmpmmP 2)(232)32(1 ,23 p что противоречит предположению об отсутствии простых чисел на интервале ).322,32(  pmm Отсюда получаем  122)32(1 pmmP .12)1(2  pm Таким образом, справедливость неравенства (30) в этом случае доказана.  .ˆ)1( ppmp  Гарантированная оценка для ближайшего простого числа, превышающего ,32 m будет иметь вид  122122)32(1 pmpmmP .1ˆ22  pm Если число 32 m не является простым, то  )12(1 mP  122122)32()22( 11 pmpmmPmP 12)1(2  pm и неравенст- во (30) в этом случае доказано. Пусть 32 m — простое число. Проведя рассуждения, аналогичные первому случаю, получаем, что число 322  pm не может быть ближайшим простым числом, превышающим .32 m Следовательно, имеем ,5ˆ22522)32(1  pmpmmP что свидетель- ствует о справедливости неравенства (30). Утверждение доказано. Предложенное представление неотрицательных рациональных чисел ),,( nkr ,, Znk  ,1),(0  nkr введенные операции на последовательностях простых чи- сел специального вида и полученные оценки для границ интервалов, содержащих ближайшие простые числа, дают возможность обосновать методику для формали- зации и исследования величин меры принадлежности нечетких множеств, изло- женную в [6]. Заключение В настоящей работе рассмотрены специальные последовательности про- стых чисел, их свойства, введены операции на рассматриваемых последователь- ностях, получены оценки для интервалов размещения ближайших к заданному числу простых чисел. Предложен алгоритм для приближения произвольного ра- ционального числа с помощью элементов введенных последовательностей про- стых чисел. Доказано, что решение, полученное с помощью предложенного алгоритма, является оптимальным решением рассматриваемой задачи при- ближения произвольного рационального числа. Рассмотрено множество неот- рицательных рациональных чисел, которые представляются в виде отноше- ния двух простых чисел из введенных последовательностей. Для этого мно- жества получены нижнее и верхнее сопряженные множества, установлены соотношения между элементами различных множеств. Приведены и доказаны утверждения для оценок интервалов размещения ближайших к заданному це- лому простых чисел. Полученные результаты позволяют обосновать методи- ку построения треугольных нечетких чисел в виде интервалов, границы кото- рых выбираются с помощью элементов специальных последовательностей простых чисел, и были предложены в работе [6]. 118 ISSN 0572-2691 Є.В. Івохін, Д.О. Вадньов ПРО ДЕЯКІ ВЛАСТИВОСТІ ТА ОЦІНКИ ДЛЯ ПОСЛІДОВНОСТЕЙ ПРОСТИХ ЧИСЕЛ Розглянуто спеціальні послідовності простих чисел, їх властивості, введено операції на розглянутих послідовностях, отримано оцінки для інтервалів роз- міщення найближчих до заданого числа простих чисел. Запропоновано алго- ритм для наближення довільного раціонального числа за допомогою елементів введених послідовностей простих чисел. Доведено твердження для оцінок інте- рвалів розміщення найближчих до заданого цілого простих чисел. Отримані ре- зультати дозволяють обгрунтувати методику побудови трикутних нечітких чи- сел у вигляді інтервалів, границі яких обираються за допомогою елементів спе- ціальних послідовностей простих чисел. E V. Ivokhin, D.A. Vadnev ON THE PROPERTIES AND ESTIMATES FOR THE PRIME NUMBERS SEQUENCES The specific sequences of prime numbers, their properties, operations introduced on these sequences are considered. The estimates for arrangement intervals of the prime numbers the closest to the specified number are obtained. An algorithm to approximate an arbitrary ra- tional number using elements of introduced sequences of primes is proposed. The statement for estimates of arrangement intervals of the closest to specified integer prime numbers. are proved. The obtained results enable us to substantiate the method of constructing triangular fuzzy numbers in the form of intervals the boundaries of which are selected using the mem- bers of special sequences of prime numbers. 1. Нестеренко Ю.В. Алгоритмические проблемы теории чисел. Введение в криптографию / Под ред. В.В. Ященко. — СПб. : Питер, 2001. — 288 с. 2. Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспек- ты. — М. : Либроком, 2011. — 664 с. 3. Генри С. Уоррен, мл. Алгоритмические трюки для программистов. — М. : Вильямс, 2007. — 288 с. 4. Iwaniec H. On the error term in the linear sieve // ACTA Arithmetica. — 1971. — N 19. — P. 1–30. 5. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М. : МЦНМО, 2003. — 328 с. 6. Івохін Є.В. Про застосування спеціальних множин простих чисел для визначення міри належності нечітких множин // Журнал обчислювальної та прикл. математики. — 2013. — № 4. — С. 1–8. Получено 04.06.2015. Статья представлена к публикации членом редколлегии чл.-корр. НАНУ А.А. Чикрием.

О некоторых свойствах и оценках для последовательностей простых чисел

Institution

Ähnliche Einträge