Remarks on a sequence of minimal Niven numbers H. Fredricksen1, E. J. Ionascu2, F. Luca3 and P. Sta˘nica˘1 1 Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943, USA; {HalF,pstanica}@nps.edu 2 Department of Mathematics, Columbus State University, Columbus, GA 31907, USA; ionascu [email protected] 3 Instituto de Matem´aticas, Universidad Nacional Aut´onoma de M´exico, C.P. 58089, Morelia, Michoac´an, M´exico; fl[email protected] Abstract. Inthisshortnoteweintroducetwonewsequencesdefinedusingthesumofdigits intherepresentationofanintegerinacertainbase.AconnectiontoNivennumbersisproposed and some results are proven. Mathematics Subject Classification: 11A07, 11B75, 11L20, 11N25, 11N37, 11Y55 Key Words: sum of digits, sequences, Niven numbers. 1 Introduction A positive integer n is called a Niven number (or a Harshad number) if it is divisible by the sum of its decimal digits. For instance, 2007 is a Niven number since 9 divides 2007. A q-Niven number is one which is divisible by the sum of its base q digits (incidentally, 2007 is also a 2-Niven number). Niven numbers have been extensively studied by various authors (see [1–5,7,8,10], just to cite a few of the most recent works). We let s (k) be the sum of q digits of k in base q. In this note, we define two sequences in relation to q-Niven numbers. For a fixed but arbitrary k ∈ N and a base q ≥ 2, we ask if there exists a q-Niven number whose sum of its digits is precisely k. Therefore it makes sense to define a to be the smallest positive k multiple of k such that s (a ) = k. In other words, a is the smallest Niven number whose q k k sum of the digits is a given positive integer k (trivially, for every k such that 1 ≤ k < q we have a = k). We invite the reader to check that, for instance, a = 48 in base 10. k 12 In [6] we remarked that q-Niven numbers with only 0’s or 1’s in their q-base representa- tion, with a fixed sum of digits, do exist. So, we define b as the smallest positive multiple k WorkbyF.L.wasdoneintheSpringof2007whilehevisitedtheNavalPostgraduateSchool.Hewould like to thank this institution for its hospitality. H. F. acknowledges support from the National Security Agency under contract RMA54. Research of P. S. was supported in part by a RIP grant from Naval Postgraduate School. Report Documentation Page Form Approved OMB No. 0704-0188 Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. 1. REPORT DATE 3. DATES COVERED 2007 2. REPORT TYPE 00-00-2007 to 00-00-2007 4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER Remarks on a sequence of minimal Niven numbers 5b. GRANT NUMBER 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) 5d. PROJECT NUMBER 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION Naval Postgraduate School,Department of Applied REPORT NUMBER Mathematics,Monterey,CA,93943 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S) 11. SPONSOR/MONITOR’S REPORT NUMBER(S) 12. DISTRIBUTION/AVAILABILITY STATEMENT Approved for public release; distribution unlimited 13. SUPPLEMENTARY NOTES SEQUENCES 2007, Springer-Verlag LNCS 4893, 162?168, 2007 14. ABSTRACT In this short note we introduce two new sequences defined using the sum of digits in the representation of an integer in a certain base. A connection to Niven numbers is proposed and some results are proven. 15. SUBJECT TERMS 16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF ABSTRACT OF PAGES RESPONSIBLE PERSON a. REPORT b. ABSTRACT c. THIS PAGE Same as 8 unclassified unclassified unclassified Report (SAR) Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std Z39-18 of k, which written in base q has only 0’s or 1’s as digits, and in addition s (b ) = k. q k Obviously, a and b depend on q, but we will not make this explicit to avoid complicating k k the notation. Clearly, in base 2 we have a = b for all k but for q > 2 we actually expect k k a to be a lot smaller than b . k k 2 The Results We start with a simple argument (which is also included in [6]) that shows that the above sequencesarewelldefined.Firstweassumethatksatisfiesgcd(k,q) = 1.ByEuler’stheorem, we can find t such that qt ≡ 1 (mod k), and then define K = 1+qt+q2t+···+q(k−1)t. Obviously, K ≡ 0 (mod k), and so K = kn for some n and also s (K) = k. Hence, in this q case, K is a Niven number whose digits in base q are only 0’s and 1’s and whose sum is k. This implies the existence of a and b . k k If k is not coprime to q, we can assume that k = ab where gcd(b,q) = 1 and a divides qn for some n ∈ N. As before, we can find a multiple of b, say K, such that s (K) = b. Let q u = max{n,dlog Ke}+1, and define q K0 = (qu+q2u+···+qua)K. Certainly k = ab is a divisor of K0 and s (K0) = ab = k. Therefore, a and b are well q k k defined for every k ∈ N. However, this argument gives a large upper bound, namely of size exp(O(k2)) for a . In k thecompanionpaper[6],wepresentconstructivemethodsbytwodifferenttechniquesforthe binary and nonbinary cases, respectively, yielding sharp upper bounds for the numbers a k and b . Here we point out a connection with the q-Niven numbers. The binary and decimal k cases are the most natural cases to consider. The table below describes the sequence of minimal Niven numbers a for bases q = 2,3,5,7,10, where k = 2,...,25. k 2 k base 2 base 3 base 5base 7base 10 2 6 4 6 8 110 3 21 15 27 9 12 4 60 8 8 16 112 5 55 25 45 65 140 6 126 78 18 12 24 7 623 77 63 91 133 8 2040 80 24 32 152 9 1503 1449 117 27 18 10 3070 620 370 40 190 11 3839 1133 99 143 209 12 16380 2184 324 48 48 13 16367 3887 949 325 247 Table 1. Values of a in various bases k 14 94206 4130 574 1022 266 15 96255 30615 4995 195 195 16 1048560 6560 624 832 448 17 483327 19601 2873 629 476 18 524286 177138 3114 342 198 19 1040383 58805 6099 1273 874 20 4194300 137780 15620 1700 3980 21 5767167 354291 12369 9597 399 22 165 15070 347732 12474 2398 2398 23 16252927 529253 31119 6509 1679 241342177201594320 15624 2400 888 25 665845751417175781225 10975 4975 We remark that if m is the minimal q-Niven number corresponding to k, then q − 1 must divide m−s (m) = kc −k = (c −1)k. This observation turns out to be useful in q k k the calculation of a for small values of k. For instance, in base ten, a can be established k 17 easily by using this simple property: 9 has to divide c −1 and so we check for c the 17 17 values 10, 19, and see that 28 is the first integer of the form 9m+1 (m ∈ N) that works. In some cases, one can find a explicitly, as our next result shows. In [6] we proved the n following result. Lemma 1 If q > 2, then (cid:18) (cid:19) qm−1 aqm = qm 2q q−1 −1 . If q = 2, then a = 2m(22m −1). 2m The first part of the following lemma is certainly known, but we include a short proof for completeness. 3 Lemma 2 Let q ≥ 2 and k, n be positive integers. Then s (nk) ≤ s (k)s (n). In particular, q q q k = s (a ) ≤ s (k)s (a /k). A similar inequality holds for b , and both such inequalities q k q q k k are sharp regardless of the base q. Proof. Write X X n = n qi, and k = k qj, where n ,k ∈ {0,1,...,q−1}, i j i j i=0 j=0 forallindicesiandj.Certainly,theproductnk = P P n k qi+j isnotnecessarilythe i=0 j=0 i j baseq expansionofnk,asacertainvalueofi+j mayoccurmultipletimes,orsomeproducts P P n k mayexceedq.However,s (nk) ≤ n k = s (k)s (n),whichimpliesthefirst i j q i=0 j=0 i j q q assertion. Letusshowthattheinequalitiesaresharpineverybaseq.Ifq = 2,thenlettingk = 2m, we get, by Lemma 1, that a = 2m(22m −1), s (a ) = 2m, s (k) = 1, and s (a /k) = 2m, 2m 2 k 2 2 k which shows that indeed s (a ) = s (k)s (a /k). Similarly, Lemma 1 implies that this 2 k 2 2 k inequality is sharp for an arbitrary base q as well. (cid:3) Let us look at the base 2 case. In [6], we have shown that Theorem 3 For all integers k = 2i−1 ≥ 3, we have a ≤ 2k+k− +2k −2k−i−1, (1) k where k− is the least positive residue of −k modulo i. Furthermore, the bound (1) is tight when k = 2i−1 is a Mersenne prime. Weextendthepreviousresultinournexttheorem,whoseproofissimilartotheproofof Theorem 3 in [6] using obvious modifications for the second claim, however we are going to include it here for the convenience of the reader. It is worth mentioning that, as a corollary of this theorem, the value of a is known for every k which is an even perfect number (via k the characterization of the even perfect numbers due to the ancient Greeks, see Theorem 7.10 in [9]). Theorem 4 For all integers k = 2s(2i−1) ≥ 3, with i,s ∈ Z, i ≥ 2, s ≥ 0, we have a ≤ 2s(2k+k− +2k −2k−i−1), (2) k 4 where k− is the least nonnegative residue of −k modulo i. Furthermore, the bound (2) is tight when 2i−1 is a Mersenne prime. Proof. For the first claim, it suffices to show that the sum of binary digits of the upper bound on (2) is exactly k, and also that this number is a multiple of k. Indeed, from the definition of k−, we find that k+k− = ia for some positive integer a. Since 2k+k− +2k −2k−i−1=2k−i(2i−1)+2ia−1 =(2i−1)(2k−i+2i(a−1)+2i(a−2)+···+1), we get that 2s(2k+k− +2k −2k−i−1) is divisible by k. For the sum of the binary digits we have (cid:16) (cid:17) (cid:16) (cid:17) s 2k+k− +2k −2k−i−1 =s 2k+k−−1+···+2+1+2k −2k−i (cid:16) (cid:17) =s 2k+k−−1+···+2k +···+2dk−i+···+2+1+2k (cid:16) (cid:17) =s 2k+k− +2k−1+···+2dk−i+···+2+1 =k, where tˆmeans that t is missing in that sum. The first claim is proved. We now consider that p = 2i −1 is a Mersenne prime. Then we need to show that the right hand side of (2) is the smallest number that satisfies the conditions mentioned above. The divisibility condition implies that a = 2sx for some x ∈ N. We need to show that k x = 2k+k− +2k−2k−i−1, or in other words, x is the smallest number that has the sum of its digits in base 2 equal to k and it is divisible by p. Weknowthata ≥ 2k−1.Letusdenotebymthefirstpositiveintegerwiththeproperty k that 2k+m−1 ≡ 2j1 +2j2 +...+2jm (mod p) (3) for some 0 ≤ j < ... < j ≤ k + m − 2. Notice that any other m0 > m will have this 1 m property and if we denote by y = 2j1 +2j2 +...+2jm the ak = 2s(2k+m−1−y) where j1, j ,..., j are chosen to maximize y. Because 2 m x = 2k+k−+1−1−(2k−i+2k+k−−1+2k+k−−2+...+2k) ≡ 0 (mod p) we deduce that m ≤ k− +1. Let us show that m < k− +1 leads to a contradiction. It is enough to show that m = k− leads to a contradiction. 2k+k− ≡ 2ia ≡ 1 (mod p). Hence 5 0 ≡ 2j1 +2j2 +...+2jm (mod p). Because 2i ≡ 1 (mod p), we can reduce all powers 2j of 2 modulo p to powers with exponents less than or equal to i−1. We get at most m ≤ i−1 such terms. But in this case, the sum of at least one and at most i−1 distinct members of the set {1,2,...,2i−1} is positive and less than the sum of all of them, which is p. So, the equality (3) is impossible in this case. Therefore m = k− +1 and one has to choose j , j ,...,j in order to maximize y. This 1 2 m means j = k+m−1, j = k+m−2, ..., and finally j has to be chosen in such a way m m−1 1 it is the greatest exponent less than k such that 2k+m−1−y ≡ 0 (mod p). Since j = k−i 1 satisfies this condition and because the multiplicative index of 2 (mod p) is i this choice is precisely the value for j which maximizes y. 1 (cid:3) Next, we find by elementary methods an upper bound on a . k Theorem 5 If k is a 2-Niven number, then 2is(k/s+1)−1 a ≤ k , k 2is −1 where s = s (k) and i is the largest nonzero binary digit of k. Moreover, the equality 2 s s (a ) = s (k)s (a /k) holds for at least 2 k 2 2 k (cid:18) (cid:19) N N 2log2 +O logN (logN)9/8 integers k ≤ N. Proof. The observation allowing us to construct a multiple kd of k such that s (kd ) = k k 2 k out of any 2-Niven number k, is to observe that we may choose d such that if s (kd ) = k, k 2 k then s (d ) = k/s (k). Thus, if 2 k 2 N K X X k = k 2i and d = n 2j, i k j i=0 j=0 then kd = PN PK k n 2i+j. The equality holds if this is indeed the binary expansion k i=0 j=0 i j of kd , that is, if i+j are all distinct for all choices of i and j such that k n 6= 0. k i j 6 This argument gives us a way to generate d . Let k ,k ,...,k be all the nonzero k i1 i2 is binary digits of k, where s = s (k). Put m = k/s. Recall that d must be odd, and so the 2 k least nonzero digit of d is 1. We shall define a sequence of disjoint sets in the following k way. Set d = 0, and 1 A = {i ,i ,...,i }. 1 1 2 s Now, let d = min{d ∈ N|d−i +i 6∈ A ,‘ = 1,...,s}−i and set 2 1 ‘ 1 1 A = {d +i ,d +i ,...,d +i }. 2 2 1 2 2 2 s Next, let d = min{d ∈ N|d−i +i 6∈ A ∪A ,‘ = 1,...,s}−i and set 3 1 ‘ 1 2 1 A = {d +i ,d +i ,...,d +i }. 3 3 1 2 2 3 s Continue the process until we reach d = min{d ∈ N|d−i +i 6∈ A ∪A ∪···∪A ,‘ = m 1 ‘ 1 2 m−1 1,...,s}−i and set 1 A = {d +i ,d +i ,...,d +i }. m m 1 m 2 m s Further, we define d = 2d1 +2d2 +2d3 +···+2dm. (4) k Next, observe that s m m X X X X kd = 2il 2dp = 2t, k ‘=1 p=1 r=1t∈Ar and so the binary sum of digits of kd is s (kd ) ≤ Pm P 1 = ms = k, since the k 2 k r=1 t∈Ar cardinality of each partition set A is s. r Regarding the bound on a , the worst case that can arise would be to take d = ji at k j s every step in the construction of the sequence of sets A . Thus, an upper bound for a is j k given by 2is(m+1)−1 a ≤ 1+2is +···+2m·is = . k 2is −1 We now observe that if the equality s (a ) = s (k)s (a /k) holds, since k = s (a ), 2 k 2 2 k 2 k then k is a 2-Niven number. Finally, the last estimate follows from the previous observation together with Theorem D of [7] concerning the counting function of the 2-Niven numbers. (cid:3) 7 LetusconsideranexampletoillustratetheapproachofTheorem5.Letn = 34 = 21+25. Thus, s = 2, i = 1,i = 5. Now, the sequence of the sets A , where i = 1,..., 34 = 17 runs 1 2 i 2 as follows: {1,5},{2,6},{3,7},{4,8},{9,13},{10,14},{11,15},{12,16},{17,21}, {18,22},{19,23},{20,24},{25,29},{26,30},{27,31},{28,32},{33,37}. Subtracting i = 1 from the smallest element of each set A , we can define 1 i d = 20+21+22+23+28+29+210+211+216+217+218+219+224+225+226+227+232. 34 Itisimmediatethats (34d ) = 34(weinvitethereadertocheckthata isstrictlysmaller 2 34 34 than d ). 34 One can introduce a new restriction on Niven numbers in the following way: we define a strongly q-Niven number to be a q-Niven number whose base q digits are all 0 or 1. Obviously, every 2-Niven number is a strongly 2-Niven number. Other examples include q+q2+···+qq, or q+q3+q5+···+q2q+1, which are both strongly q-Niven numbers for any base q. The related problem of investi- gating the statistical properties of the strongly q-Niven numbers seems interesting and we shall pursue this elsewhere. References 1. T. Cai, ‘On 2-Niven numbers and 3-Niven numbers’, Fibonacci Quart. 34 (1996), 118–120. 2. C. N. Cooper and R. E. Kennedy, ‘On consecutive Niven numbers’, Fibonacci Quart. 21 (1993), 146–151. 3. J. M. De Koninck and N. Doyon, ‘On the number of Niven numbers up to x’, Fibonacci Quart. 41.5 (2003)m 431–440. 4. J. M. De Koninck, N. Doyon, and I. Katai, ‘On the counting function for the Niven numbers’, Acta Arith. 106 (2003), 265–275. 5. H. G. Grundman, ‘Sequences of consecutive Niven numbers’, Fibonacci Quart. 32 (1994), 174–175. 6. H. Fredricksen, E.J. Ionascu, F. Luca, P. Stanica, ‘Minimal Niven numbers (I)’, submitted 2007. 7. C. Mauduit, C. Pomerance and A. S´ark¨ozy, ‘On the distribution in residue classes of integers with a fixed digit sum’, The Ramanujan J. 9 (2005), 45–62. 8. C. Mauduit and A. S´ark¨ozy, ‘On the arithmetic structure of integers whose sum of digits is fixed’, Acta Arith. 81 (1997), 145–173. 9. K. H. Rosen.‘Elementary Number Theory’ (5th Ed.), 2005. 10. I.Vardi,‘Nivennumbers’,§2.3inComputational Recreations in Mathematics,Addison-Wesley,1991, pp. 19 and 28–31. 8