Sum of digits of x and powers of x

[mart_r]

Given a base b >= 2 and an odd integer exponent n >= 3, consider the difference (or ratio) between the sum of the last d digits (in base b) of x and the sum of the last d digits of x^n, where x mod b <> 0.
How quickly/efficiently can one find the minimum (or maximum) of these quantities for all possible values of x (0 < x < b^d)? Are there any "interesting" solutions or ways of solving?
(This is a generalization of the ideas that lead to e.g. A122484 or A138597. A very old question of mine, that I haven't asked anyone yet, is "is there an x such that the sum of digits of x^5 is less than or equal to the sum of digits of x?")


In case this sounds too complicated to start thinking about, here's already a follow-up question on another subject:
We know that the sum of the reciprocals of primes <= p is ~ log(log(p))+M with M=0.2614972...; how do the asymptotics look like for the sum of the reciprocals of semiprimes, or k-almost primes - beside the predominant term log(log(p))^k?

[slandrum]

Originally Posted by mart_r

A very old question of mine, that I haven't asked anyone yet, is "is there an x such that the sum of digits of x^5 is less than or equal to the sum of digits of x?")

I assume you are not looking for trivial answers like x = 0, or x = 10^y

[JeppeSN]

You will be interested in the thread Integers n for which the digit sum of n exceeds the digit sum of n^5 in which I once wrote comments. /JeppeSN

[mart_r]

Originally Posted by slandrum

I assume you are not looking for trivial answers like x = 0, or x = 10^y

Nope. I just phrased the question as simply as possible.

Originally Posted by JeppeSN

You will be interested in the thread Integers n for which the digit sum of n exceeds the digit sum of n^5 in which I once wrote comments. /JeppeSN

Interesting indeed! Thanks
I was in fact typing the question into mathstackexchange but didn't get this particular result... maybe also because I used "x" instead of "n".

[Dr Sardonicus]

I'm afraid I'm pretty much drawing a blank on this one. However, I did notice a couple of minor things.

If the base b = p, a prime number, or p > 2 is prime and b = p^e or 2*p^e, the multiplicative group of integers mod p is cyclic.

If gcd(x, b) = 1 the multiplicative order of x^n will depend to some extent on gcd(n, eulerphi(b)).

If the base b has at least two prime factors, there will be "automorphs" to the base b. If b = A*B with A > 1, B > 1, and gcd(A,B) = 1 then for any positive integer k, the Chinese Remainder Theorem insures that there is a simultaneous solution to the congruences

x == 0 (mod A^k), x == 1 (mod B^k). Such x are called base-b "automorphs." They are not relatively prime to the base b.

If x is a k-digit automorph, we have x^2 == x (mod b^k), and x ≠ 0, 1 (mod b). Note that b^k + 1 - x satisfies x == 1 (mod A^k) and x == 0 (mod B^k), so automorphs occur in pairs.

To the base b = 2*5, there are two automorphs, ...6259918212890625 and ...3740081787109376.

Now if n is odd, x^n - x is divisible by x^2 - x, so if x is a k-digit automorph, x^n and x will have the same last k digits. So if k > 1, n > 1 is odd, x is a k-digit automorph, and d is the number of digits in x^n, then d > k, so x^n will have a larger digit sum than x.

[mart_r]

Ah yes, the automorphs
I dug out some calculations of mine from 2010 - man, it's already been twelve years! -, where I found that if b is the product of exactly k distinct primes or prime powers, then there will be 2^k-2 automorphs in base b. I have a nice printout with the last 100 digits of automorphs of each base b <= 36. For example, for b = 30, there are six automorphs: ...LB2J6 / ...OH13A / ...E1Q7F / ...FS3MG / ...5CSQL / ...8IRAP.
I'm sure there are also extensive lists on the web, but it's late and I'm too lazy to dig them up...

[mart_r]

All this talk about automorphs made me kinda hungry and I tried to find primes in the sequences A214882 and A214883.

In A214882, a(n) is prime for n = {3, 5, 7, 9, 11, 12, 14, 23, 41, 69, 78, 223, 264, 293, 294, 312, 314, 316, 555, 624, 917, 1750, 2183, 2266, 4858, ...}
In A214883, a(n) is prime for n = {1, 2, 3, 5, 6, 27, 191, 206, 220, 3499, ...}
(tested up to n=5000 in both cases)

What could we call them? Autoprimes? Primorphs? 10-adic automorph prime thingies?

[mart_r]

Just out of curiosity: would it impress anyone to have 100+ digit integers not ending in zero whose digital sum is larger than the digital sum of their cubes?

[mart_r]

Has even any work been done toward proving or disproving the infinitude of integers <> 0 mod b such that the digit sum in base b is larger than the digit sum of their cube?
I was working my way through some figures that suggest these numbers might be finite (at least for base 10; contrary to what I used to believe for a long time).

BTW, I noticed that there is a user on math.stackexchange named "Martin R" - that is not me, just in case someone is curious.

[mart_r]

Looking through various works concerning the sum of digits of different functions (a rather recent one being "The sum of digits of floor(n^c)" by J. Morgenbesser: see here), the one I'm looking for still seems elusive. Probably I'm overlooking something. The papers all seem concerned with the distribution of digits rather than certain extreme cases:
For \(s_b(n)\) denoting the sum of digits for a given base \(b \geq 2\) and positive integer n, let \(\Delta_b(d) := \max(n<b^d, n \mod b \neq 0: s_b(n)-(s_b(n^3 \mod b^d)))\).
For \(d \to \infty\), \(\Delta_b(d)\) appears to exhibit a linear asymptotic behaviour: \(\Delta_b(d) \sim d \cdot v(b)\) for some variable \(v\) depending on \(b\):

v(2) ~ 0.78
v(3) ~ 1.57
v(4) ~ 2.4
v(5) ~ 3.3
v(6) ~ 4.1
v(7) ~ 4.9
v(8) ~ 5.7
v(9) ~ 6.6
v(10) ~ 7.57
v(20) ~ 16.7
v(30) ~ 25.8
v(40) ~ 35.4
v(100) ~ 92.5

e.g. \(\Delta_2(100) = 75\) (close to \(100 \cdot 0.78\)), where, for \(n=633825300114114700575210732923\), \(s_2(n)=92\) and \(s_2(n^3 \mod 2^{100})=17\).
Has the behaviour of \(v_b\) been looked at by anyone? The values are slightly different but similar for higher odd powers other than 3, from what I've calculated so far. Confusion, lost, 1 ea.

Originally Posted by mart_r

Just out of curiosity: would it impress anyone to have 100+ digit integers not ending in zero whose digital sum is larger than the digital sum of their cubes?

200+ digits? No?

[mart_r]

Originally Posted by mart_r

Has even any work been done toward proving or disproving the infinitude of integers <> 0 mod b such that the digit sum in base b is larger than the digit sum of their cube?
I was working my way through some figures that suggest these numbers might be finite (at least for base 10; contrary to what I used to believe for a long time).

Brain malfunction, sorry. Those integers should be infinite in number. If we find an example where \(\Delta = 7.57 d\) (in fact, \(\Delta = 5 d\) would suffice), it would take about \(10^{0.054 d}\) trials to find an example, if my logic doesn't fool me (again).
In contrast, for powers of 5, it would take \(\gt 10^{2.8 d}\) trials per \(10^d\), thus almost surely there is no integer where \(s_{10}(n) \gt s_{10}(n^5)\).