вторник, 24 сентября 2013 г.

Загадка суммы цифр числовой последовательности

Одна из простых вычислительных задач привела меня к следующим вопросам.

Пусть \(s_{10}(n)\) - сумма цифр записи числа \(n\) в десятичной системе счисления, a \(ds2t(n) = s_{10}(2^{10^n})\).

Для \(n = 1,2,...,7\) я составил такую таблицу:

\(ds2t(1) = s_{10}(2^{10^1}) = 7\),
\(ds2t(2) = s_{10}(2^{10^2}) = 115\) ,
\(ds2t(3) = s_{10}(2^{10^3}) = 1366\),
\(ds2t(4) = s_{10}(2^{10^4}) = 13561 = 135\cdot10^2 + 61\),
\(ds2t(5) = s_{10}(2^{10^5}) = 135178 = 135\cdot10^3 + 178\),
\(ds2t(6) = s_{10}(2^{10^6}) = 1351546 = 135\cdot10^4 + 1546\),
\(ds2t(7) = s_{10}(2^{10^7}) = 13546438 = 135\cdot10^5 + 46438\),

далее, выяснилось, что и при \(n = 8\) для \(ds2t(n)\) сохраняется закон, который начал действовать с n = 4: \(ds2t(n) = 135\cdot10^{n-2} + r, r\ge0\).

А именно,

\(ds2t(8) = 135481777 = 135\cdot10^6 + 481777\)

это наводит на мысль, что тот же закон будет действовать и для \(n\ge9\).

Мне пока непонятно, как доказать или опровергнуть эту гипотезу, если только не пытаться найти опровержение посредством вычисления очередного \(ds2t(n)\).

В более широкой последовательности \(s_{10}(2^{n}),  n = 1, 2, 3, ... \) числа вида  \(135\cdot10^{k} + r\), вообще говоря, встречаются нечасто. 

Проверив 281686 показателей, я нашел, что только 816 из них приводит к появлению чисел вида \(135\cdot10^{k} + r\). Возникает вопрос: каков закон распределения этих чисел?

Далее представлена таблица из указанных выше 816 показателей \(2^n\).

\(n\)\(s_{10}(n)\)
10131355
10331352
975013546
975113520
975213567
975413570
980113508
980213507
980713589
980813525
981013501
982313538
985913538
986113517
987013501
989513592
989613549
989813534
989913595
990213513
990313526
990413525
991013534
991113586
991213528
991313511
992413537
993013510
993913517
994813501
995613594
997913556
998013567
998313550
998513520
998613540
998813597
998913514
999213531
999913571
1000013561
1000113532
1000313583
1000813519
1001713580
1002413543
1002713574
1003313529
1003413531
1004113544
1004213552
1005713538
1005813567
1006713514
1007313541
1007513574
1008013528
1009713514
1010413501
1010513574
1011013519
1011113592
1013313559
1013613513
1014213576
1015113559
1015513589
1015713586
1015813537
1020513568
1023613510
1025913550
1026613582
1026813531
98810135112
98999135014
99000135280
99055135335
99082135088
99093135215
99110135076
99115135200
99146135481
99147135251
99152135283
99181135137
99184135583
99185135482
99229135083
99232135466
99233135410
99240135010
99280135169
99283135785
99287135527
99288135730
99289135137
99292135214
99295135218
99299135023
99300135127
99303135098
99304135187
99315135008
99316135367
99325135020
99326135049
99331135065
99337135281
99341135068
99342135586
99343135119
99344135058
99345135530
99347135878
99348135244
99349135479
99350135427
99351135746
99352135547
99353135509
99355135209
99362135400
99363135323
99378135307
99381135044
99382135097
99387135206
99390135046
99405135314
99413135266
99425135095
99426135685
99442135169
99468135415
99475135344
99476135733
99477135305
99483135800
99484135520
99486135118
99497135221
99498135433
99499135317
99500135733
99502135007
99503135275
99504135181
99509135014
99510135307
99511135047
99519135053
99540135064
99541135047
99542135274
99544135502
99545135365
99546135577
99555135233
99562135025
99563135248
99564135604
99565135785
99568135529
99578135319
99579135530
99580135664
99581135086
99582135433
99583135101
99584135508
99585135953
99586135673
99587135500
99588135397
99591135134
99592135601
99597135098
99598135295
99599135005
99600135397
99606135721
99607135623
99608135319
99609135161
99623135266
99624135730
99625135875
99627135152
99628135142
99630135064
99631135065
99633135323
99634135457
99635135662
99637135173
99639135143
99640135052
99660135001
99661135227
99664135277
99665135131
99667135146
99668135418
99669135026
99671135698
99672135568
99673135542
99675135359
99677135878
99679135335
99680135112
99681135359
99685135209
99686135256
99687135332
99688135016
99691135119
99694135178
99695135122
99696135064
99700135097
99702135496
99707135365
99708135829
99709135119
99710135211
99711135557
99712135421
99713135671
99716135211
99717135188
99718135070
99719135365
99720135046
99721135119
99723135053
99725135662
99726135811
99727135056
99728135202
99729135485
99730135250
99731135077
99734135328
99735135413
99736135376
99737135518
99738135037
99746135265
99747135422
99748135610
99749135653
99753135449
99755135392
99756135262
99757135281
99763135119
99765135161
99766135241
99767135725
99768135163
99769135488
99770135022
99771135431
99772135448
99773135185
99774135307
99775135092
99776135355
99778135529
99779135230
99781135119
99783135008
99784135043
99785135113
99788135850
99789135683
99790135745
99792135433
99793135713
99794135283
99795135548
99796135502
99797135059
99798135631
99799135551
99804135082
99807135638
99809135491
99810135631
99813135899
99815135635
99818135121
99819135629
99821135023
99822135352
99823135911
99824135292
99825135278
99826135268
99828135289
99829135290
99830135526
99831135620
99832135448
99833135950
99834135667
99837135674
99843135152
99846135217
99847135821
99848135904
99849135341
99850135277
99855135431
99856135934
99857135482
99858135622
99859135866
99860135013
99862135097
99864135118
99865135308
99866135139
99867135548
99869135104
99877135245
99878135535
99879135638
99880135187
99881135680
99885135854
99886135565
99887135509
99889135533
99890135157
99891135044
99896135418
99897135539
99899135212
99900135514
99901135785
99902135481
99903135764
99904135916
99905135509
99906135721
99907135272
99908135607
99909135476
99910135952
99912135451
99918135874
99919135731
99920135076
99922135358
99923135167
99925135911
99926135301
99929135068
99930135082
99937135119
99938135463
99939135026
99940135205
99941135743
99942135793
99943135398
99944135265
99949135191
99950135382
99951135215
99954135082
99955135182
99958135169
99959135752
99960135703
99961135056
99962135301
99963135548
99966135253
99967135299
99968135850
99970135664
99971135095
99973135695
99974135823
99975135044
99976135754
99977135698
99978135334
99979135380
99980135589
99981135323
99982135700
99983135293
99984135478
99986135013
99987135629
99991135182
99993135107
99995135032
99996135415
99997135416
99998135526
99999135629
100000135178
100001135716
100005135701
100007135806
100008135730
100009135542
100010135013
100012135205
100013135383
100014135586
100015135272
100016135733
100017135098
100018135133
100019135752
100022135850
100023135827
100024135187
100025135842
100027135722
100028135121
100029135440
100030135295
100031135284
100032135523
100033135938
100034135913
100035135350
100036135844
100037135887
100038135973
100039135524
100040135202
100041135908
100043135869
100046135706
100047135161
100049135347
100050135712
100052135688
100053135008
100055135626
100056135424
100057135623
100058135967
100060135682
100061135320
100062135145
100063135218
100064135769
100065135719
100066135727
100067135383
100068135919
100070135688
100071135404
100072135943
100073135806
100074135640
100075135182
100076135229
100078135178
100079135374
100080135262
100081135668
100082135607
100086135811
100087135308
100089135350
100090135223
100091135005
100092135343
100094135778
100095135377
100096135844
100097135860
100098135334
100099135155
100101135080
100102135790
100104135775
100105135758
100106135985
100110135028
100113135413
100114135475
100115135203
100116135559
100117135884
100118135733
100120135268
100124135904
100125135998
100126135637
100127135644
100128135838
100129135902
100130135850
100131135566
100132135466
100134135676
100141135731
100143135890
100147135668
100148135778
100149135674
100153135857
100159135263
100161135701
100162135259
100163135401
100164135658
100165135875
100166135679
100167135890
100168135979
100174135889
100175135329
100176135487
100177135452
100178135247
100179135422
100180135403
100181135617
100182135559
100183135956
100184135724
100185135845
100186135673
100187135419
100188135793
100189135893
100197135962
100198135412
100199135302
100200135793
100201135488
100202135760
100203135800
100204135988
100205135743
100206135901
100207135740
100208135724
100209135449
100210135277
100211135167
100212135352
100213135416
100216135880
100217135194
100218135271
100219135218
100220135355
100221135575
100222135214
100223135842
100224135847
100225135326
100226135706
100229135491
100230135352
100231135272
100236135100
100237135956
100238135643
100239135899
100240135862
100245135665
100246135241
100247135239
100248135766
100252135466
100253135446
100254135478
100256135598
100257135413
100258135439
100259135104
100260135253
100261135713
100262135598
100263135386
100264135475
100265135608
100267135578
100276135997
100277135887
100279135974
100280135355
100281135494
100282135331
100283135797
100287135773
100289135608
100290135892
100298135697
100303135839
100306135610
100307135437
100308135442
100309135749
100310135445
100311135548
100312135286
100314135145
100315135182
100316135454
100317135854
100318135727
100319135347
100320135244
100321135551
100322135508
100324135790
100326135667
100327135695
100329135206
100331135293
100332135946
100334135967
100335135998
100337135896
100338135955
100339135389
100340135418
100341135593
100343135977
100344135766
100345135650
100347135881
100349135725
100350135325
100351135686
100352135526
100353135395
100354135880
100360135763
100368135568
100369135236
100371135467
100374135406
100375135938
100383135485
100384135925
100385135590
100386135325
100387135389
100390135808
100394135715
100395135692
100396135394
100413135854
100419135827
100420135592
100421135716
100422135361
100423135353
100424135310
100425135404
100426135628
100427135041
100428135478
100429135884
100430135382
100431135242
100432135070
100433135518
100434135541
100435135398
100437135665
100438135736
100439135725
100442135976
100443135827
100444135430
100445135887
100446135721
100449135890
100450135655
100451135824
100452135910
100453135821
100455135647
100456135898
100460135985
100461135395
100462135718
100463135347
100464135208
100465135065
100466135193
100467135521
100468135844
100470135370
100471135344
100472135553
100478135661
100479135917
100483135794
100487135923
100489135920
100495135515
100498135691
100500135784
100502135877
100503135926
100506135316
100507135713
100508135427
100509135737
100511135545
100512135550
100513135812
100514135868
100517135950
100520135733
100521135728
100522135493
100523135212
100524135838
100547135752
100548135793
100549135875
100557135764
100561135542
100562135067
100563135836
100571135869
100572135262
100573135065
100575135719
100580135562
100583135707
100584135406
100585135947
100586135652
100612135952
100613135797
100614135271
100615135839
100624135934
100625135455
100626135208
100627135344
100633135974
100645135803
100646135697
100647135845
100648135790
100649135743
100650135874
100651135992
100655135473
100657135695
100658135949
100659135836
100662135955
100665135989
100666135601
100678135952
100679135743
100690135934
100695135989
100699135884
100701135962
100712135832
100756135862
100759135947
100760135958
100761135791
100762135790
100764135991
100789135785
100792135943
100800135865
100804135907
100805135896
100813135704
100814135931
100819135767
100836135928
100837135686
100838135787
100840135502
100853135995
100872135883
100873135893
100905135926
100930135691
100955135968
100956135973
100965135926
100966135628
100967135716
100971135782
100972135799
100984135988
100985135842
100988135823
100997135860
100998135730
101013135773
101014135808
101015135680
101017135938
101020135790
101468135832
101469135872

7 комментариев:

  1. Чтобы понять закономерность, если она конечно есть, нужно начать с самых простых степеней. Смею предположить, что последовательность, грубо говоря, не имеет никакой закономерности, кроме той, которая имеется при непосредственном вычислении суммы цифр. Таким образом, может получиться, что задача не решаема, говоря проще, есть только одно решение: найти сумму цифр. А последовательность со множителем 135 это просто частный случай общей последовательности.

    ОтветитьУдалить
    Ответы
    1. Все правильно говорите.

      Но определенная регулярность в распределении сумм цифр последовательности степеней должна быть. Вопрос в том, какой характер у этой регулярности? Как его оценивать? Нужно исследовать распределение, чтобы точно сказать, будет появляться 135 далее или нет.

      Задача конечно не мейнстримная (работ по сумме цифр я нашел вообще не очень много, хотя к серьезным поискам пока еще не приступал) и не прикладная, - пока что из разряда головоломок. Но она очень интересная в инженерном плане, т.к. быстро приводит к необходимости применения нетривиальных алгоритмов.

      Вычислить в лоб ds2t(9) и ds2t(10) было бы уже здорово :)

      Удалить
  2. Написал программу перемножения в десятичной арифметике. ds2t(5) вычислил за 1 минуту. ds2t(6) уже 20 минут вычисляется. Буду думать, что можно оптимизировать.
    А PARI/GP ds2t(9) уже не может вычислить.

    ОтветитьУдалить
    Ответы
    1. Старушка Maxima сдулась на n = 8. На каком языке написана ваша программа? Я считал ds2t(8) крайне примитивным скриптом на Python, заняло много часов (около 16 или даже 18). Основные потери, думаю, были при перегоне из символьного в целочисленный тип. Хотя и сама степень надо думать считалась долго.

      Удалить
    2. Значение ds2t(6) вычислилось за 36 минут. Пишу в среде разработки Lazarus (free pascal). Еще есть перспективы для оптимизации, я только сегодня начал писать!

      Удалить
    3. Путем некоторых ухищрений ускорил вычисления ds2t(8) более, чем в 3 раза (было более 19 часов, стало 5). И это еще явно не предел.

      ds2t(8) = 135481777

      real 320m57.210s
      user 320m23.483s
      sys 0m1.650s

      Удалить
    4. Пишу в разных комментариях то про 16-18 часов, то >19 - показания расходятся, давно это было :) Но точно не меньше 16 часов. Оба раза считал на одном и том же компьютере, скриптом на Python 2.7.6.

      Удалить