Степени двойки, третья степень и простые числа
От: notree Россия  
Дата: 23.09.17 12:36
Оценка: 10 (1)
Ложью свет пройдёшь, да назад не вернёшься.
Re: Степени двойки, третья степень и простые числа
От: T4r4sB Россия  
Дата: 23.09.17 12:39
Оценка:
Здравствуйте, notree, Вы писали:

Нахрена слово "наименьшее" перед x?
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[2]: Степени двойки, третья степень и простые числа
От: notree Россия  
Дата: 23.09.17 12:45
Оценка:
первое встречное x, начиная перебирать x по порядку 1,2,3,4,5,6,...
Ложью свет пройдёшь, да назад не вернёшься.
Re[3]: Степени двойки, третья степень и простые числа
От: T4r4sB Россия  
Дата: 23.09.17 12:53
Оценка:
Здравствуйте, notree, Вы писали:


N>первое встречное x, начиная перебирать x по порядку 1,2,3,4,5,6,...

Докажи, что такие x вообще есть.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re: Степени двойки, третья степень и простые числа
От: T4r4sB Россия  
Дата: 23.09.17 12:56
Оценка:
Здравствуйте, notree, Вы писали:

N>Image: 00.png

Спойлер.
  Скрытый текст
Если число x делится на p*p-2*p+1, то 2^x-x^3 делится на p
Если число x делится на q*q-q, то 2^x-x^3 делится на q с остатком 1.
  Скрытый текст
Берём икс, которое делится на p*p-2*p+1 для нашего q и на q*q-q для любого простого q<p



правка: исправил грубую ошибку в формулировке
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Отредактировано 26.09.2017 18:53 T4r4sB . Предыдущая версия .
Re[4]: Степени двойки, третья степень и простые числа
От: notree Россия  
Дата: 23.09.17 12:58
Оценка:
К сожалению доказать сам не могу, поэтому попросил о помощи. Убедило меня в этом большое количество примеров, подтверждающих утверждение.
Ложью свет пройдёшь, да назад не вернёшься.
Re[4]: Степени двойки, третья степень и простые числа
От: kov_serg Россия  
Дата: 23.09.17 22:34
Оценка: +1
Здравствуйте, T4r4sB, Вы писали:

TB>Докажи, что такие x вообще есть.

"Для любого простого p, есть наименьшее x
такое, что наименьший делитель 2^x-x^3 равен p"


При x=p+8 выражение 2^x-x^3 всегда делится на p

[ 2^(p+8)-(p+8)^3 ]%p = 0

[ 2^(p+8) = (p+8)^3 ]%p
[ 2^(p+8-p+1) = 8^3 ]%p
[ 2^9 = 2^9 ]%p

А раз есть хоть какой-то x то есть и наименьший.
Над остальными надо подумать днём.
Re[5]: Степени двойки, третья степень и простые числа
От: T4r4sB Россия  
Дата: 26.09.17 07:31
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>При x=p+8 выражение 2^x-x^3 всегда делится на p

О, круто! А теперь сделай так, чтобы она не делилось ни на какое меньшее p.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[6]: Степени двойки, третья степень и простые числа
От: kov_serg Россия  
Дата: 26.09.17 18:12
Оценка:
Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, kov_serg, Вы писали:

_>>При x=p+8 выражение 2^x-x^3 всегда делится на p

TB>О, круто! А теперь сделай так, чтобы она не делилось ни на какое меньшее p.

Для любого простого p есть x1=p+2, x2=p+8, x3=2p+4 которые всегда делают выражение 2^x-x^3 кратным p
Re[7]: Степени двойки, третья степень и простые числа
От: T4r4sB Россия  
Дата: 26.09.17 18:26
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Для любого простого p есть x1=p+2, x2=p+8, x3=2p+4 которые всегда делают выражение 2^x-x^3 кратным p
По условию ещё надо, чтоб оно не делилось ни на какое меньшее простое число.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[6]: Степени двойки, третья степень и простые числа
От: kov_serg Россия  
Дата: 26.09.17 18:45
Оценка:
Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, kov_serg, Вы писали:

_>>При x=p+8 выражение 2^x-x^3 всегда делится на p

TB>О, круто! А теперь сделай так, чтобы она не делилось ни на какое меньшее p.

Ваше утверждение не верно
Вот пример p=29 x=31

2^x-x^3 = 2^31-31^3 = 2147453857 = 23*29*59*197*277

Оно делится на 23
Отредактировано 26.09.2017 18:53 kov_serg . Предыдущая версия .
Re[8]: Степени двойки, третья степень и простые числа
От: kov_serg Россия  
Дата: 26.09.17 18:48
Оценка:
Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, kov_serg, Вы писали:

_>>Для любого простого p есть x1=p+2, x2=p+8, x3=2p+4 которые всегда делают выражение 2^x-x^3 кратным p
TB>По условию ещё надо, чтоб оно не делилось ни на какое меньшее простое число.

Для этого надо что бы p-6 было не простым числом.
Re[7]: Степени двойки, третья степень и простые числа
От: T4r4sB Россия  
Дата: 26.09.17 18:48
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Ваше утверждение не верно

Какое именно утверждение?
И это, почему твой ответ не имеет никакого отношение к цитате. Расскажи, как получить число, для которого f(x) делится на p, но не делится ни на какое q меньшее p.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[9]: Степени двойки, третья степень и простые числа
От: T4r4sB Россия  
Дата: 26.09.17 18:51
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Для этого надо что бы p-6 было не простым числом.

То есть ты хочешь сказать, что для p=11 ответа нет?
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[10]: Степени двойки, третья степень и простые числа
От: kov_serg Россия  
Дата: 26.09.17 18:59
Оценка:
Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, kov_serg, Вы писали:

_>>Для этого надо что бы p-6 было не простым числом.

TB>То есть ты хочешь сказать, что для p=11 ответа нет?
Я хочу сказать что
p=11 x=p+2=13
2^13-13^3 = 5995 и оно делится на 5, а 5 меньше чем 11

еще отдельно частный случай для 3
p=3 x=2*p+4=10 2^x-x^3=24 но он не интересен
Re[11]: Степени двойки, третья степень и простые числа
От: T4r4sB Россия  
Дата: 26.09.17 19:01
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Я хочу сказать что
_>p=11 x=p+2=13
_>2^13-13^3 = 5995 и оно делится на 5, а 5 меньше чем 11

Да, значит твоё решение не позволяет найти ответ для p=11.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[8]: Степени двойки, третья степень и простые числа
От: kov_serg Россия  
Дата: 26.09.17 19:04
Оценка:
Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, kov_serg, Вы писали:

_>>Ваше утверждение не верно

TB>Какое именно утверждение?
Утверждение что p наименьший множитель.

TB>И это, почему твой ответ не имеет никакого отношение к цитате. Расскажи, как получить число, для которого f(x) делится на p, но не делится ни на какое q меньшее p.
Если is_prime(p-6)=0 тогда у f(p+2) минимальный длитель p
Re[12]: Степени двойки, третья степень и простые числа
От: kov_serg Россия  
Дата: 26.09.17 19:09
Оценка:
Здравствуйте, T4r4sB, Вы писали:

TB>Здравствуйте, kov_serg, Вы писали:

_>>Я хочу сказать что
_>>p=11 x=p+2=13
_>>2^13-13^3 = 5995 и оно делится на 5, а 5 меньше чем 11

TB>Да, значит твоё решение не позволяет найти ответ для p=11.
Причем тут моё решение для p=11 есть 3 решения x=13,19,26 все эти решения делают f(x) кратными 11
наименьшее 13 даёт 5995, оно делится на 11 но еще и на 5 которое меньше чем 11.
Т.е. заявленое утверждение в постановке задачи ложно.
Убрать противоречие можно потребовав is_prime(p-6)=0 тогда всё пучком.
Re[9]: Степени двойки, третья степень и простые числа
От: T4r4sB Россия  
Дата: 26.09.17 20:06
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Утверждение что p наименьший множитель.

Это не я утверждал, это условие задачи, читайте внимательно!

_>Если is_prime(p-6)=0 тогда у f(p+2) минимальный длитель p

А если нет?
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[9]: Степени двойки, третья степень и простые числа
От: kov_serg Россия  
Дата: 26.09.17 20:06
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Если is_prime(p-6)=0 тогда у f(p+2) минимальный длитель p
Хотя нет это не достаточное условие
p=31 x=p+2=33 f(x)=2^x-x^3=8589898655=5*13*31*43*99139
Тут и 5 и 13 < 31

Для любого простого p, есть наименьшее x, такое, что наименьший делитель 2^x-x^3 равен p

Пусть p=29 то x=37 f(x)=29*4739272511 -- 29 наименьший делитеть
...

Если же уменьшать число 31 на y, то наименьший делитель
2^(31-y)-(31-y)^3 не будет равен p=23 ни для одного такого
y<31.


f(x-y)
f(36)=2^6*5*7*29*937*1129
f(31)=23*29*59*197*277
f(24)=2^9*29*1129
f(22)=2^3*3*29*6011
вот

  таблица нескольких первых f(x) 
x    f(x)
-    ----
10    2^3*3
11    3*239
12    2^6*37
13    5*11*109
14    2^3*5*11*31
15    7*13*17*19
16    2^12*3*5
17    3*11*3823
18    2^3*7*23*199
19    11*17*2767
20    2^6*71*229
21    13*19*79*107
22    2^3*3*29*6011
23    3*2792147
24    2^9*29*1129
25    17*23*31*2767
26    2^3*11*762401
27    5*19*97*14563
28    2^6*3*223*6269
29    3*178948841
30    2^3*7*13*71*20773
31    23*29*59*197*277
32    2^15*131071
33    5*13*31*43*99139
34    2^3*3*5*143165249
35    3*5925107*1933
36    2^6*5*7*29*937*1129
37    29*4739272511
38    2^3*17*127*15914651
39    7*31*37*139*263*1873
40    2^9*3*157*283*16111
41    3*229*3200907113
42    2^3*19*733*8171*4831
43    41*307*11597*60259
44    2^6*131*16187*129629
45    37*43*761*29059957
46    2^3*3*2932031003347
47    3*5*31*997*142589*2129
48    2^12*13*1291501*4093
49    41*47*292138014169
50    2^3*23*6119021232161
51    7*11*19*31*43*277*4168459
52    2^6*3*173*7103539*19087
53    3*5*1086623231*552611
54    2^3*5*17183408857*26209
55    47*53*4868255713*2971
56    2^9*5*491*57326879167
57    7*631*1657*524231*37561
58    2^3*3*99799307*120337499
59    3*1381279*52957*2626901
60    2^6*7*4278367*37447*16063
61    53*59*127*5806282112899
62    2^3*29*1379742970499*14407
63    61*461*72101289109*4549
64    2^18*3*47*2796203*178481
65    3*11*30698966381*36417659
66    2^3*31*61*1109*435759013*10093
67    5*59*58107873939443*8609
68    2^6*59*14553724753*5370733
69    61*67*8388539*17217842671
70    2^3*3*739*66564705723805309
71    3*3766223*77600773961*2693
72    2^9*7*11547631*2097143*54409
73    5^3*71*1064195263745272117
74    2^3*5*1442662665737*327336847
75    67*73*1559*1610131*21523*142969
76    2^6*3*5*127*197*70707636899*44491
77    3*17*13309543381919*222626231
78    2^3*7^2*37*13277791*33554393*46771
79    29^2*71*10123141628968106159
80    2^12*295147905179352825731
81    7*73*79*271*23209*32497*50671*5783
82    2^3*3*11*157*885823520590601*131707
83    3*105376466597*150885983*202757
84    2^6*17*2947782217*3947579*1527793
85    83*359*1298306078721620753431
86    2^3*41*235887964802854473111461
87    5^2*79*127*659*169957*169032397*32587
88    2^9*3*277*7418054701862171*98057
89    3*2418095517386146603*85324727
90    2^3*13*43*53*79*6648588511*548761*18121
91    83*89*32051945704568584703*10457
92    2^6*32468003548189788997559*2383
93    5*7^3*67940537527*67878271*1252177
94    2^3*3*5^3*4431959354344957*1489712867
95    3*3574565800719269*3694069290799
96    2^15*5^2*43*173*126682645777*31033*3307
97    29*89*167*367625056037159331520037
98    2^3*17*47*727*84932196794519*172199*4663
99    7*97*163*684495073*6817891*342679*3581
100    2^6*3*11*59*18070603*216852832597*2596067
101    3*845100400152152934331135126817
102    2^3*7*37*61*367*709*24266791*27367*15161*15313
103    31*101*197*16408546537793*1002005594831
104    2^9*39614081257132168796771972971
105    19*73*97*103*1618705635517423*1808407277
106    2^3*3*109*95101160663481941921*326103893
107    3*5*5019838499734586021317177*2154907
108    2^6*11*47*59*563219*29201976076393*10107121
109    101*107*60057102555459744014649027469
110    2^3*53*3061495789230440818709019058901
111    103*109*20709609541*8855448139*1260907829
112    2^12*3*422550200076076467165567735011
113    3*5*29*101*929777*1957196337924995743*129887
114    2^3*5*7*13*37*83*167*1983103*5610176994152836711
115    43*107*113*397*156770998289*1283697200196017
116    2^6*5*2707903611306012969517223999*95873
117    37*109*199*8168417701837262808517*25344881
118    2^3*3*103800707828772551934624073*133391431
119    3*1481*502790133135727*57735945442613*5153
120    2^9*7*13*17^2*37*824582553997*88447543*18191*2011
121    113*845566337006048326180316087*27822961
122    2^3*59*799875312935848771209793187531*14083
123    7^2*11*13*269*67848163*420223927*63499*1166663*2671
124    2^6*3*11*10069909058976635400786417123335041
125    3*31*43*1390387*14781311*2332846755671*24533*9043
126    2^3*61*3126168357016363*2199023255489*25358143
127    5*11*599*117216562394202353*44058626761714657
128    2^21*162259276829213363391578010288127
129    11*127*3253*24889*272257*6296415907*3510015719173
130    2^3*3*8419*418273*1106652366137*14553137642258879
131    3*31*3041*9625649936062018746334139022796489
132    2^6*93967*2106919*4398046511071*97700420845369
133    5*109*131*157*3797*104472799*2448940003535831042399
134    2^3*5*51913621*81527563680853*128639291991943529
135    7*13*107*127*479*415799*176848577041447166447304967
136    2^9*3*5*11*46523*385997*7412269*45414353*170580569633
137    3*147594437*3141399156364499*125254990894452371
138    2^3*19*67*16231*507449119*118068331369*35184372088763
139    131*137*923534840531*2217433581227*18961541036071
140    2^6*11572026258279463*1881958353435160683881843
141    7*13*131*139*3231589*1074331972177*484559685379977133
142    2^3*3*31*43*739*2003*331692299*354941856875081472989581
143    3*31*11321*10590626231074339504914607391843097517
144    2^12*7*13*19*223*601*2683*16981*4194301*4200451*29271545137
145    101*137*264333976727*16564791658703*736153638022531
146    2^3*71*107*2834063*15801210001*32775355302794544778781
147    5*19*23*139*739*6624109589*1489933269427*80538651929731
148    2^6*3*53*83*173*20639*3326069*35572808867868127669128481
149    3*359*147319*892435433*5039855483791847353632104297
150    2^3*29*73*5641*33739*265594201*85883516947*19412067359353
151    17*43*149*277*40429*201893*24600203*471186652151585458009
152    2^9*31*10687961*56260663*3086752425901*193787688194153
153    5*139*151*8329*389002249*8504523015739*3948504611989813
154    2^3*3*5*41*194870353*43091387461*409271224477*1350537877501
155    3*17*41*21842145464653618457133022966228524325320023
156    2^6*5*7*11911105957*32168568766931*106425935996589112669
157    149*691*555257*955641857*303535264667*11016576206906407
158    2^3*21499*144305425357*14721376126458964019932182539503
159    151*157*293*59778929989*195804422833*8987821858061733307
160    2^15*3*31*198323*415201*348625009995187*16706151244732199
161    3*11*17*1246754490623*25491274131989*163943406979351520813
162    2^3*7*47*79*103*32063*132337327*853865993*75341257746369034423
163    2129*11159*112631546302235273*4369465430091252030808187
164    2^6*31*59*1471*2972141*45692353488842633261577264928607417
165    7*37*157*163*402551*863287*570071329*24651133093*1444841033227
166    2^3*3*131*400151*82599383*900110925239634232182928440797309
167    3*5*89*9511*12119*6915011899*175809407893675231608215633869
168    2^9*14633*57073*615540166387*4377911406469*324699687117301
169    31*167*1889*3631*11897*262524771577*753014512769*8960284476961
170    2^3*83*38406983*28669999832337301*2046884323688281080304027
171    13*163*691*13499*228635498587*10675989930799*62039293084293919
172    2^6*3*223*120691*6417859139*180504525980526230445064749850297
173    3*5^2*23*107*1229*19142971*2757116697861090391226267914156174411
174    2^3*5*17*127*1279*1747*3229*74471*22766886451*22666490899158485543623
175    11*167*173*1372414343*109801616431259516897825754735477279151
176    2^12*5*11396927609*286599881236811437*1431810321286787287829
177    7*13*23*43*491*569*1093*6679*12289*44231617*1919980527254117689455769
178    2^3*3*27045806321*590239204847000092559480454057183391404173
179    3*58505438429*76336177700028558461*57190161205559447381807
180    2^6*31*10105481*28522182779*2679895152792169516995318325630711
181    173*179*1637*1907*6586913*1570924082641530923*3064034025277220113
182    2^3*89*558972821913109*15402404505135049313768207654463393617
183    7*181*277*5071177*10936691977*20596544359*67254716257*454695824897
184    2^9*3*1748483771*9129907570273358254254440851093104405311177
185    3*7329473*32950109*1022432460996211*66200871817489362510266747
186    2^3*7*13*67801*216379*2374717*4002547*6330702467*152614711852696183423
187    5^2*179*2010730961*21800285655086196779202075328009883875787767
188    2^6*31*137869*629569*2278177489215976056262446425491569129480491
189    13^2*19*151*181*1811347*104911789*267999799883*175554891204629430109207
190    2^3*3*2833*21347*959978597*706458730777*1594249034629987679242239229
191    3*4523*3271039*70712404820578624728473663023582426156738739647
192    2^18*11*77888017*26202761468337431*1066617856461247985311772281
193    5*191*13145762796621320971383852195199301394978754857516295117
194    2^3*5^2*31*83*173*883627361779*5879876814103*54283256169084813037360387
195    193*12613*308849*816667*2761999*119454776112013*247887831124682552737
196    2^6*3*5^2*3889*41278152067*82256484310799*1584563250285286751870878993
197    3*23*497051*1615351*2987725619*1213532710807862016967362208047749809
198    2^3*7*97*619*19793*1863966460234381*3238463547990021097989188120707693
199    191*197*1909490420992633*11182838672403799904450796398702481467779
200    2^9*127*52426679*490610756782532923542871*960806731078504764051161
Отредактировано 26.09.2017 23:01 kov_serg . Предыдущая версия . Еще …
Отредактировано 26.09.2017 22:55 kov_serg . Предыдущая версия .
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.