4
$\begingroup$

This question is for those who have wondered what it means to decimate an army when the number of soldiers is not a multiple of ten.

I am interested in really good upper bounds on the length of a certain finite sequence. I will define the sequence and then show what is, I think, a pretty good upper bound on its length. A colleague of mine suggested that one should be able to do better, and I realize that I don't know much about what kind of tools ought to be brought to bear on this type of elementary, but nontrivial problem.

By $\mathbb{N}$ I mean the natural numbers: $\{0,1,2,\ldots\}$. Let $d$ be a positive integer, and consider the "$d$-decimation function"

$D_d: N \mapsto N - \lceil \frac{N}{d} \rceil$.

You can think about this function as follows (and this is how it arises in my intended application): we have $N$ discrete objects and we place each into one of $d$ boxes. Then we are allowed to remove all the objects from any one box. If we want to minimize the number of objects remaining, we simply choose the box which has the most (or tied for the most) objects. By the Pigeonhole Principle at least one box must have $\frac{N}{d}$ objects. But because everything is integer-valued, there must in fact be a box with at least $\lceil \frac{N}{d} \rceil$ objects, hence if we empty that box we are left with at most $D_d(N)$ objects.

Now we redistribute the remaining objects in the (still $d$ -- we don't remove the box, just empty it) boxes and repeat. Thus for $i \geq 1$ define

$D_d^i = D_d \circ \ldots \circ D_d: \mathbb{N} \rightarrow \mathbb{N}$, the $i$-fold composition. Because $D_d(N) < N$ for all $N \geq 1$, for each $N \in \mathbb{Z}^+$ there is some $i$ such that $D_d^i(N) = 0$. We define the d-decimation length of $N$ to be the least such $i$ and denote it by $\ell_d(N)$. I want really good upper bounds on $\ell_d(N)$.

Some quick comments:

  • For all $N \in \mathbb{Z}^+$ we have $D_1(N) = 0$, so $\ell_1(N) = 1$.
  • For all $N \leq d$ we have $D_d(N) = N-1$, so $\ell_d(N) = N$ if $d \geq N$.

So the interesting case is $2 \leq d < N$: let's assume that.

I will now give the upper bound that I know. It comes from the fact that

$D_d(N) = N - \lceil \frac{N}{d} \rceil \leq N - \frac{N}{d} = (1-\frac{1}{d})N$,

so

$D_d^i(N) \leq N (1-\frac{1}{d})^i$.

Since $e^x$ is convex, it lies above its tangent line, thus $1+x \leq e^x$ for all $x$, with strict inequality for all $x \neq 0$. Using this we get

$N (1-\frac{1}{d})^i < N e^{\frac{-i}{d}}$

If we choose $i$ such that

$N e^{\frac{-i}{d}} < d$, then $D_d^i(N) < d$, so $D_d^{i+d-1} = 0$ and $\ell_d(N) \leq i + d-1$. An easy calculation shows that we can take

$i = \lceil d \log \frac{N}{d} \rceil$,

so $\ell_d(N) \leq \lceil d \log \frac{N}{d} \rceil + d-1 < d (1+\log \frac{N}{d})$.

I would like to do better than this. My colleague says that one can get instead

$\ell(d) \leq d(\gamma + \epsilon + \log \frac{N}{d})$,

where $\gamma = 0.577\ldots$ is the Euler-Mascheroni constant and $\epsilon$ approaches $0$ as $\min(d,\frac{N}{d})$ approaches infinity. (I certainly believe him; I just don't understand how to get this.) He also suggests a better bound involving partial sums of the harmonic series which is valid in all cases. More than anything, I would like to see how someone who knows what they are doing attacks this kind of problem.

$\endgroup$
4
$\begingroup$

Your colleague is correct. The letter $L$ will denote where we are now, $D$ is your $D.$ Then $H_k$ is the harmonic sum including $1/k.$

If $D \geq L,$ each step will subtract exactly $1,$ so there are at most $D$ steps.

If $2D \geq L > D,$ each step will subtract exactly $2,$ so there are at most $D/2$ steps to reach $D \geq L,$ so at most $D H_2$ steps to reach $0.$

If $3D \geq L > 2D,$ each step will subtract exactly $3,$ so there are at most $D/3$ steps to reach $2D \geq L > D,$ so at most $D H_3$ steps to reach $0.$

If $4D \geq L > 3D,$ each step will subtract exactly $4,$ so there are at most $D/4$ steps to reach $3D \geq L > 2D,$ so at most $D H_4$ steps to reach $0.$

If $5D \geq L > 4D,$ each step will subtract exactly $5,$ so there are at most $D/5$ steps to reach $4D \geq L > 3D,$ so at most $D H_5$ steps to reach $0.$

...................

If $wD \geq L > (w-1)D,$ each step will subtract exactly $w,$ so there are at most $D/w$ steps to reach $(w-1)D \geq L > (w-2)D,$ so at most $D H_w$ steps to reach $0.$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Ca y est! Thanks a million. $\endgroup$ – Pete L. Clark Nov 6 '14 at 3:28
2
$\begingroup$

Same program except that I restricted to $n=d^2,$ I had not noticed the part about $d$ and $n/d$ being large. Now the part about $\gamma \approx 0.5772156649$ begins to seem realistic. I think the final column always comes out below $0.577$ this time.

   N        D        L      (L/D) - log(N/D)
10000      100      517     0.5648298140119086
10201      101      523     0.5630973049409189
10404      102      529     0.5613016965196507
10609      103      535     0.5594457690519176
10816      104      541     0.5575321777817039
11025      105      547     0.5555634593662863
11236      106      554     0.5629760002275555
11449      107      560     0.5608160253511776
11664      108      566     0.5586095136165208
11881      109      572     0.5563585397892046
12100      110      579     0.5631559978439474
12321      111      585     0.560740068957936
12544      112      592     0.5672154144191911
12769      113      598     0.5646475795177477
12996      114      604     0.5620471656405919
13225      115      610     0.559415697723706
13456      116      617     0.5653753261350144
13689      117      623     0.5626123899885684
13924      118      629     0.559823850110606
14161      119      636     0.5654143220145207
14400      120      643     0.5708415905512874
14641      121      648     0.5595813552297051
14884      122      655     0.5648314142831368
15129      123      661     0.5617993844649809
15376      124      668     0.5668152085885112
15625      125      674     0.5636862626976992
15876      126      681     0.5684799978104271
16129      127      687     0.5652617324390466
16384      128      693     0.5620322360803829
16641      129      700     0.5665441847856145
16900      130      706     0.5632347803136486
17161      131      712     0.5599171806156426
17424      132      719     0.5641677743833264
17689      133      725     0.5607786913271182
17956      134      732     0.564846767213268
18225      135      738     0.5613918882282374
18496      136      745     0.5652862907345358
18769      137      751     0.5617708989893934
19044      138      758     0.5654999380312015
19321      139      764     0.5619289445671496
19600      140      771     0.5655004345335528
19881      141      777     0.5618784074941719
20164      142      784     0.5652997029621193
20449      143      790     0.5616308942156168
20736      144      797     0.5649089226462217
21025      145      803     0.5611972920621839
21316      146      810     0.564338583771116
21609      147      817     0.5673905424729645
21904      148      823     0.5635985370466955
22201      149      830     0.5665234927122587
22500      150      837     0.5693647059037443
22801      151      843     0.5655016201387184
23104      152      850     0.5682247423116183
23409      153      856     0.5643333204376295
23716      154      863     0.5669435014824747
24025      155      869     0.5630264959839791
24336      156      876     0.5655286081350779
24649      157      883     0.5679580163077432
24964      158      889     0.5639872454540457
25281      159      896     0.5663159235659316
25600      160      903     0.5685761847661729
25921      161      909     0.564558367934792
26244      162      916     0.5667246524219371
26569      163      922     0.5626915169846489
26896      164      929     0.5647677185172654
27225      165      936     0.5667817988266922
27556      166      943     0.5687351032097214
27889      167      949     0.5646409181221669
28224      168      956     0.5665122110729318
28561      169      962     0.562408977384619
28900      170      969     0.5642015629497384
29241      171      976     0.5659387826786264
29584      172      983     0.5676218022563143
29929      173      990     0.5692517581033772
30276      174      997     0.5708297582567355
30625      175     1003     0.5666425975050573
30976      176     1010     0.5681523685982115
31329      177     1016     0.5639632617764537
31684      178     1023     0.5654074609438701
32041      179     1030     0.5668041382933228
32400      180     1037     0.5681542602209007
32761      181     1043     0.5639339079606932
33124      182     1050     0.5652240821539738
33489      183     1057     0.566470131311585
33856      184     1064     0.5676729380431882
34225      185     1071     0.5688333641108643
34596      186     1078     0.5699522510179817
34969      187     1084     0.5656828269956808
35344      188     1091     0.566749526531753
35721      189     1098     0.567776794464167
36100      190     1105     0.5687654015237245
36481      191     1111     0.564480498654941
36864      192     1119     0.5706296279722185
37249      193     1125     0.5663253551365655
37636      194     1132     0.5671933873284242
38025      195     1139     0.5680260824618939
38416      196     1146     0.568824116279687
38809      197     1153     0.5695881494346002
39204      198     1160     0.5703188278913238
39601      199     1166     0.5659916576875678
40000      200     1173     0.5666826334519636
   N        D        L      (L/D) - log(N/D)
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Looks good. Now -- how do you prove it?!? $\endgroup$ – Pete L. Clark Nov 6 '14 at 2:20
  • 1
    $\begingroup$ @PeteL.Clark, done. $\endgroup$ – Will Jagy Nov 6 '14 at 3:27
1
$\begingroup$

I don't see it; please check the first few values, see if i am doing what you intended; the most likely error is being off by 1 in the L column every time.

    N        D        L     (L/D) - log(N/D)

    3        2        2     0.5945348918918356

    4        2        3     0.8068528194400547
    4        3        3     0.7123179275482191

    5        2        3     0.5837092681258449
    5        3        4     0.8225077095673425
    5        4        4     0.7768564486857903

    6        2        3     0.4013877113318903
    6        3        4     0.640186152773388
    6        4        5     0.8445348918918356
    6        5        5     0.8176784432060454

    7        2        3     0.247237031504632
    7        3        4     0.4860354729461296
    7        4        5     0.6903842120645773
    7        5        6     0.8635277633787871
    7        6        6     0.8458493201727416

    8        2        4     0.6137056388801094
    8        3        5     0.6858374136549406
    8        4        6     0.8068528194400547
    8        5        6     0.7299963707542644
    8        6        7     0.8789845942148858
    8        7        7     0.8664686073754775

    9        2        4     0.4959226032237259
    9        3        5     0.5680543779985571
    9        4        6     0.6890697837836712
    9        5        7     0.8122133350978809
    9        6        7     0.7612015585585024
    9        7        8     0.8915427145762367
    9        8        8     0.8822169643436165

   10        2        4     0.3905620875658996
   10        3        5     0.4626938623407307
   10        4        6     0.5837092681258449
   10        5        7     0.7068528194400546
   10        6        8     0.8225077095673425
   10        7        8     0.7861821989184103
   10        8        9     0.9018564486857903
   10        9        9     0.8946394843421737

   11        2        4     0.2952519077615748
   11        3        5     0.3673836825364059
   11        4        7     0.7383990883215201
   11        5        7     0.6115426396357296
   11        6        8     0.7271975297630178
   11        7        9     0.8337291619712286
   11        8        9     0.8065462688814654
   11        9       10     0.9104404156489599
   11       10       10     0.904689820195675

   12        2        4     0.208240530771945
   12        3        6     0.6137056388801094
   12        4        7     0.6513877113318903
   12        5        8     0.7245312626461002
   12        6        9     0.8068528194400547
   12        7        9     0.7467177849815989
   12        8       10     0.8445348918918356
   12        9       10     0.8234290386593303
   12       10       11     0.9176784432060455
   12       11       11     0.9129886230103703

   13        2        4     0.1281978230984086
   13        3        6     0.533662931206573
   13        4        7     0.5713450036583538
   13        5        8     0.6444885549725637
   13        6        9     0.7268101117665183
   13        7       10     0.8095322201652051
   13        8       10     0.7644921842182992
   13        9       11     0.854497442096905
   13       10       11     0.837635735532509
   13       11       12     0.9238550062459245
   13       12       12     0.9199572923264636

   14        2        4     0.05408985094468669
   14        3        6     0.459554959052851
   14        4        7     0.497237031504632
   14        5        8     0.570380582818842
   14        6        9     0.6527021396127963
   14        7       10     0.7354242480114833
   14        8       11     0.8153842120645773
   14        9       11     0.780389469943183
   14       10       12     0.8635277633787871
   14       11       12     0.8497470340922028
   14       12       13     0.9291826535060749
   14       13       13     0.9258920278462782

   15        2        4     -0.01490302054226476
   15        3        6     0.3905620875658996
   15        4        8     0.6782441600176805
   15        5        9     0.7013877113318904
   15        6       10     0.7503759347925116
   15        7       10     0.6664313765245319
   15        8       11     0.7463913405776259
   15        9       12     0.8225077095673425
   15       10       12     0.7945348918918356
   15       11       13     0.8716632535143425
   15       12       13     0.8601897820191235
   15       13       14     0.9338222332824037
   15       14       14     0.9310071285130486

   16        2        5     0.4205584583201641
   16        3        6     0.3260235664283285
   16        4        8     0.6137056388801094
   16        5        9     0.6368491901943192
   16        6       10     0.6858374136549406
   16        7       11     0.7447499982441035
   16        8       12     0.8068528194400547
   16        9       12     0.7579691884297715
   16       10       13     0.8299963707542645
   16       11       13     0.8071247323767712
   16       12       14     0.8789845942148858
   16       13       14     0.8692837121448324
   16       14       15     0.9378971788040489
   16       15       15     0.9354614788624288

   17        2        5     0.3599338365037292
   17        3        6     0.2653989446118936
   17        4        8     0.5530810170636745
   17        5        9     0.5762245683778844
   17        6       10     0.6252127918385056
   17        7       11     0.6841253764276687
   17        8       12     0.7462281976236198
   17        9       13     0.8084556777244477
   17       10       13     0.7693717489378297
   17       11       14     0.8374092014694272
   17       12       14     0.8183599723984509
   17       13       15     0.8855821672514744
   17       14       15     0.877272556987614
   17       15       16     0.9415035237126607
   17       16       16     0.9393753781835652

   18        2        5     0.3027754226637806
   18        3        7     0.5415738641052785
   18        4        8     0.4959226032237259
   18        5        9     0.5190661545379357
   18        6       11     0.7347210446652236
   18        7       11     0.6269669625877199
   18        8       12     0.6890697837836712
   18        9       13     0.7512972638844991
   18       10       14     0.8122133350978809
   18       11       14     0.7802507876294785
   18       12       15     0.8445348918918356
   18       13       15     0.8284237534115259
   18       14       16     0.8915427145762367
   18       15       16     0.8843451098727121
   18       16       17     0.9447169643436165
   18       17       17     0.9428415861600514

   19        2        5     0.2487082013935049
   19        3        7     0.4875066428350028
   19        4        8     0.4418553819534501
   19        5       10     0.6649989332676599
   19        6       11     0.6806538233949478
   19        7       12     0.7157568841745869
   19        8       13     0.7600025625133955
   19        9       13     0.6972300426142233
   19       10       14     0.7581461138276052
   19       11       15     0.8170926572682936
   19       12       15     0.7904676706215599
   19       13       16     0.8512796090643272
   19       14       16     0.8374754933059609
   19       15       17     0.896944555269103
   19       16       17     0.8906497430733408
   19       17       18     0.9475978943015403
   19       18       18     0.9459327787297243

   20        2        5     0.1974149070059543
   20        3        7     0.4362133484474521
   20        4        9     0.6405620875658996
   20        5       10     0.6137056388801094
   20        6       11     0.6293605290073973
   20        7       12     0.6644635897870365
   20        8       13     0.7087092681258449
   20        9       14     0.757047859337784
   20       10       15     0.8068528194400547
   20       11       15     0.7657993628807431
   20       12       16     0.8225077095673425
   20       13       16     0.7999863146767765
   20       14       17     0.8576107703469817
   20       15       17     0.8456512608815524
   20       16       18     0.9018564486857903
   20       17       18     0.8963045999139898
   20       18       19     0.9501950398977292
   20       19       19     0.9487067056124495

   21        2        5     0.1486247428365223
   21        3        7     0.3874231842780202
   21        4        9     0.5917719233964677
   21        5       10     0.5649154747106774
   21        6       11     0.5805703648379653
   21        7       12     0.6156734256176045
   21        8       13     0.659919103956413
   21        9       14     0.7082576951683519
   21       10       15     0.7580626552706227
   21       11       16     0.8079182896204021
   21       12       16     0.7737175453979106
   21       13       17     0.8281192274304214
   21       14       17     0.8088206061775498
   21       15       18     0.8635277633787871
   21       16       18     0.8530662845163582
   21       17       19     0.9063379651563225
   21       18       19     0.9014048757282972
   21       19       20     0.9525481203903857
   21       20       20     0.951209835830568

   22        2        5     0.1021047272016295
   22        3        7     0.3409031686431274
   22        4        9     0.5452519077615747
   22        5       10     0.5183954590757844
   22        6       12     0.7007170158697392
   22        7       12     0.5691534099827117
   22        8       14     0.7383990883215201
   22        9       14     0.6617376795334591
   22       10       15     0.7115426396357297
   22       11       16     0.7613982739855093
   22       12       17     0.8105308630963513
   22       13       17     0.7815992117955286
   22       14       18     0.8337291619712286
   22       15       18     0.8170077477438943
   22       16       19     0.8690462688814654
   22       17       19     0.8598179495214296
   22       18       20     0.9104404156489599
   22       19       20     0.9060281047554929
   22       20       21     0.9546898201956751
   22       21       21     0.9534799843651071

   23        2        5     0.05765296463079562
   23        3        7     0.2964514060722934
   23        4        9     0.5008001451907409
   23        5       10     0.4739436965049508
   23        6       12     0.6562652532989053
   23        7       13     0.6675587902690209
   23        8       14     0.6939473257506862
   23        9       15     0.7283970280737365
   23       10       16     0.7670908770648962
   23       11       16     0.7169465114146755
   23       12       17     0.7660791005255173
   23       13       18     0.8140705261477716
   23       14       18     0.7892773994003948
   23       15       19     0.8392226518397269
   23       16       19     0.8245945063106316
   23       17       20     0.8741897163623605
   23       18       20     0.8659886530781262
   23       19       21     0.9142079211320278
   23       20       21     0.9102380576248414
   23       21       22     0.9566472694133209
   23       22       22     0.9555482374291662

   24        2        5     0.01509335021199969
   24        3        7     0.2538917916534976
   24        4        9     0.458240530771945
   24        5       11     0.6313840820861549
   24        6       12     0.6137056388801094
   24        7       13     0.6249991758502249
   24        8       14     0.6513877113318903
   24        9       15     0.6858374136549406
   24       10       16     0.7245312626461002
   24       11       17     0.7652959879049704
   24       12       18     0.8068528194400547
   24       13       18     0.7715109117289757
   24       14       19     0.8181463564101703
   24       15       19     0.796663037420931
   24       16       20     0.8445348918918356
   24       17       20     0.8316301019435646
   24       18       21     0.8789845942148858
   24       19       21     0.8716483067132318
   24       20       22     0.9176784432060455
   24       21       22     0.9140876549945252
   24       22       23     0.9584431684649157
   24       23       23     0.9574403855812041

   25        2        5     -0.02572864430825544
   25        3        7     0.2130697971332423
   25        4        9     0.4174185362516898
   25        5       11     0.5905620875658998
   25        6       12     0.5728836443598542
   25        7       13     0.5841771813299698
   25        8       14     0.6105657168116352
   25        9       15     0.6450154191346854
   25       10       16     0.683709268125845
   25       11       17     0.7244739933847151
   25       12       18     0.7660308249197995
   25       13       19     0.8076119941317974
   25       14       19     0.777324361889915
   25       15       20     0.8225077095673425
   25       16       20     0.8037128973715805
   25       17       21     0.8496316368350741
   25       18       21     0.8381625996946307
   25       19       22     0.8834578911403449
   25       20       22     0.8768564486857904
   25       21       23     0.9208847080933176
   25       22       23     0.9176211739446605
   25       23       24     0.9600966519305142
   25       24       24     0.9591780054797447

    N        D        L     (L/D) - log(N/D)

Complete C++ program

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <strstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>
#include <gmp.h>
#include <gmpxx.h>

 #include "form.h"


using namespace std;


//   g++  -o pete_decimate pete_decimate.cc  -lgmp -lgmpxx


//  pete_decimate.cc   

//  William C. Jagy  


int sub(int n, int d)
{
  if( n % d == 0) return n/d;
  else return 1 + n / d;

}



int main()
{
   for(int n = 3; n <= 25; ++n){
    for(int d = 2; d <= n-1; ++d){
     int l = 0;
     int m = n;
     while ( m > 0) {
        m = m -  sub(m,  d);
       ++l;
     }  // while
     cout.precision(16);
     cout << setw(9) << n  << setw(9) << d  << setw(9) << l << "     " << 1.0 * l / d - log( 1.0 * n / d) << endl;
   } // for d
      cout << endl;
   } // for n

    return 0 ;
}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for writing some code. I was even going to try that myself. I don't yet see why you find the code unconvincing, as I'm not sure what the rate of convergence is supposed to be. The initial values look right to me (and the fact that your last column is always less than 1 is good!). What if you restrict to $d$ and $N/d$ each at least 100, for instance? $\endgroup$ – Pete L. Clark Nov 5 '14 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.