No CrossRef data available.
Article contents
RANDOM MULTIPLICATIVE WALKS ON THE RESIDUES MODULO 
$n$
Published online by Cambridge University Press: 12 May 2017
Abstract
We introduce a new arithmetic function 
$a(n)$ defined to be the number of random multiplications by residues modulo 
$n$ before the running product is congruent to zero modulo 
$n$. We give several formulas for computing the values of this function and analyze its asymptotic behavior. We find that it is closely related to 
$P_{1}(n)$, the largest prime divisor of 
$n$. In particular, 
$a(n)$ and 
$P_{1}(n)$ have the same average order asymptotically. Furthermore, the difference between the functions 
$a(n)$ and 
$P_{1}(n)$ is 
$o(1)$ as 
$n$ tends to infinity on a set with density approximately 
$0.623$. On the other hand, however, we see that (except on a set of density zero) the difference between 
$a(n)$ and 
$P_{1}(n)$ tends to infinity on the integers outside this set. Finally, we consider the asymptotic behavior of the difference between these two functions and find that 
$\sum _{n\leqslant x}(a(n)-P_{1}(n))\sim (1-\unicode[STIX]{x1D70B}/4)\sum _{n\leqslant x}P_{2}(n)$, where 
$P_{2}(n)$ is the second largest divisor of 
$n$.
MSC classification
- Type
- Research Article
- Information
- Copyright
- Copyright © University College London 2017
References
Aldous, D., Random walks on finite groups and rapidly mixing Markov chains. In Seminar on Probability, XVII
(Lecture Notes in Mathematics 986
), Springer (Berlin, 1983), 243–297; MR 770418.Google Scholar
Alladi, K. and Erdős, P., On an additive arithmetic function. Pacific J. Math.
71(2) 1977, 275–294; MR 0447086.Google Scholar
Alladi, K. and Erdős, P., On the asymptotic behavior of large prime factors of integers. Pacific J. Math.
82(2) 1979, 295–315; MR 551689.CrossRefGoogle Scholar
De Koninck, J. M. and Ivić, A., The distribution of the average prime divisor of an integer. Arch. Math. (Basel)
43(1) 1984, 37–43; MR 758338.Google Scholar
Erdős, P. and Ivić, A., Estimates for sums involving the largest prime factor of an integer and certain related additive functions. Studia Sci. Math. Hungar.
15(1–3) 1980, 183–199; MR 681439.Google Scholar
Erdős, P., Ivić, A. and Pomerance, C., On sums involving reciprocals of the largest prime factor of an integer. Glas. Mat. Ser. III
21(41)(2) 1986, 283–300; MR 896810.Google Scholar
Erdős, P. and Pomerance, C., On the largest prime factors of n and n + 1. Aequationes Math.
17(2–3) 1978, 311–321; MR 0480303.Google Scholar
Gretete, D., Random walk on a finitely generated monoid. Int. J. Math. Combinatorics
4
2011, 54–58; (electronic).Google Scholar
Hildebrand, M., A survey of results on random walks on finite groups. Probab. Surv.
2
2005, 33–63; MR 2121795.Google Scholar
Ivić, A., On the kth prime factor of an integer. Zb. Rad. Prirod.-Mat. Fak. Ser. Mat.
20(1) 1990, 63–73; MR 1158406.Google Scholar
Jeske, D. R. and Blessinger, T., Tunable approximations for the mean and variance of the maximum of heterogeneous geometrically distributed random variables. Amer. Statist.
58(4) 2004, 322–327; MR 2109423.CrossRefGoogle Scholar
Kemeny, J., Largest prime factor. J. Pure Appl. Algebra
89(1–2) 1993, 181–186.CrossRefGoogle Scholar
Knuth, D. E. and Trabb Pardo, L., Analysis of a simple factorization algorithm. Theoret. Comput. Sci.
3(3) 1976/77, 321–348; MR 0498355.CrossRefGoogle Scholar
Mairesse, J., Random walks on groups and monoids with a Markovian harmonic measure. Electron. J. Probab.
10
2005, 1417–1441 (electronic); MR 2191634.Google Scholar
McNew, N., Multiplicative problems in combinatorial number theory. PhD Thesis, Dartmouth College, 2015.Google Scholar
Wheeler, F. S., Two differential-difference equations arising in number theory. Trans. Amer. Math. Soc.
318(2) 1990, 491–523; MR 963247.Google Scholar