# Iterated integer-valued decimation

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)$.

• 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.

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$$

• Ca y est! Thanks a million. – Pete L. Clark Nov 6 '14 at 3:28

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)

• Looks good. Now -- how do you prove it?!? – Pete L. Clark Nov 6 '14 at 2:20
• @PeteL.Clark, done. – Will Jagy Nov 6 '14 at 3:27

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 ;
}


• 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? – Pete L. Clark Nov 5 '14 at 21:03