On a Generalisation of a Function of Ron Graham’s

Sarosh Adenwalla · 2025

Read On a Generalisation of a Function of Ron Graham’s by Sarosh Adenwalla (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19196.txt.

Introduction

Adenwalla wrote this number theory paper in twenty twenty-five about a function devised by Ron Graham. The function assigns to each whole number n the smallest endpoint s with a special property. Between n and s there must sit a subset whose product with n forms a perfect square. Graham posed the function in a magazine problems column in nineteen eighty-six.

Recent work proved many facts about the function and guessed a rule for when the value equals twice n. Adenwalla proves that guess in full. The paper also treats broader versions of the function built on higher powers rather than squares. It reports new results about those versions, extending the line of work that recent authors began.

Catalog record

CREATORSarosh Adenwalla
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-19196

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On a Generalisation of a Function of Ron Graham’s Sarosh Adenwalla Abstract Ron Graham introduced a function, g ⁡ ( n ) g(n) , on the non-negative integers, in the 1986 Issue 3 3 Problems column of Mathematical Magazine : For each non-negative integer n n , g ⁡ ( n ) g(n) is the least integer s s so that the integers n + 1 , n + 2 , … , s − 1 , s n+1,n+2,\ldots,s-1,s contain a subset of integers, the product of whose members with n n is a square. Recently, many results about g ⁡ ( n ) g(n) were proved in [Kagey and Rajesh, ArXiv:2410.04728, 2024] and they conjectured a characterization of which n n satisfied g ⁡ ( n ) = 2 ​ n g(n)=2n . For m ≥ 2 m\geq 2 , they also introduced generalizations of g ⁡ ( n ) g(n) to m m -th powers to explore. In this paper, we prove their conjecture and provide some results about these generalisations. 1 Introduction For non-negative integers n , define g(n) to be the smallest integer s\geq n such that there exist distinct integers a_{1},\ldots,a_{t}\in[n,s] where a_{1}=n and \prod_{i=1}^{t}a_{i} is a square. For example, g(2)=6 as 2\cdot 3\cdot 6=6^{2} . The function g(n) was introduced by Ron Graham in [ 5 ] who asked whether it was a bijection. This was shown to be true by Michael Reid in [ 8 ] , where he proved that g(n) was a bijection between \mathbb{N} and \mathbb{N}\backslash\mathbb{P} , where we say 0\in\mathbb{N} and \mathbb{P} are the primes. In [ 4 ] , Selfridge proved very strong upper bounds on g(n) , and this work led the authors in [ 2 ] to investigate the relation between g(n)-n and the largest prime factor of n , denoted P(n) . They also provided lower bounds for g(n)-n for non-square n . See Section 4 for further discussion on these bounds. A survey of known properties of the function is given by Kagey and Rajesh in [ 7 ] , and further properties are shown therein. The authors made the following conjecture. Conjecture 1.1 ( [ 7 ] ) . For all n\in\mathbb{N} , g(n)=2n if and only if: 1. n>3 is prime 2. n=0 3. n=6 . They proved the ‘if’ direction in their paper. We prove the ‘only if’ direction of the conjecture. They also suggested a generalization of g(n) to m -th powers for m\geq 2 . We prove and conjecture many analogous results for these generalized functions, g_{m}(n) . For instance, we prove upper bounds for g_{m}(n) and conjecture for which n this is tight. We also show that if m is prime, then g_{m}(n) is a bijection between \mathbb{N} and \mathbb{N}\backslash\mathbb{P} . We then prove results supporting our conjecture that, when m is composite, g_{m}(n) is neither injective nor surjective onto \mathbb{N}\backslash\mathbb{P} . Finally we investigate related functions introduced in [ 7 ] . 2 Preliminaries Here we define some notation before formally introducing the generalized function g_{m}(n) for m\geq 2 and n\in\mathbb{N} . Let \mathbb{P} be the set of primes. If we say a=x\mod m , then a\in\{0,1,\ldots,m-1\} such that a=x+km for some k\in\mathbb{Z} . We also say p^{k}||T if p^{k}|T and p^{k+1}\nmid T . An integer, w , appears s times in a sequence a_{1},\ldots,a_{t} if there exist distinct i_{1},\ldots,i_{s} such that a_{i_{j}}=w for 1\leq j\leq s and there is no other i such that a_{i}=w . We say an integer appears in a sequence if it appears s\geq 1 times in the sequence. Definition 2.1 . A sequence of integers, a_{1}\leq a_{2}\leq\ldots\leq a_{t} , is a m -product sequence if there exists R\in\mathbb{N} such that \prod_{i=1}^{t}a_{i}=R^{m} and no integer appears more than m-1 times in the sequence. Definition 2.2 . For n\in\mathbb{N} , we say g_{m}(n) is the least integer s such that there exists an m -product sequence starting at n and ending at s , that is n=a_{1}\leq\ldots\leq a_{t}=s. We call any m -product sequence that starts at n and ends with g_{m}(n) a corresponding sequence for g_{m}(n) . If a_{1}\leq a_{2}\leq\dots\leq a_{t} is a sequence where a_{i+1}=\ldots=a_{i+k} then we can write this sequence as a_{1},a_{2},\ldots,a_{i},a_{i+1}^{\{k\}},a_{i+k+1},\ldots,a_{t} . The existence of a m -product sequence starting at n and with largest term a_{t} provides an upper bound for g_{m}(n) , that is g_{m}(n)\leq a_{t} . Note that g_{2}(n)=g(n) , the function studied in [ 7 ] . The sequence (g_{2}(n))_{n=0}^{\infty} is found in the OEIS as A006255 [ 1 ] . It is useful to observe the following: Lemma 2.3 . For any m\geq 2 and n\in\mathbb{N} , g_{m}(n)=n if and only if n=k^{d} for some k,d\in\mathbb{N} where \gcd(d,m)>1 . Proof. If g_{m}(n)=n , there exists some 1\leq j\leq m-1 such that n^{\{j\}} is a corresponding sequence for g_{m}(n) . This implies that n^{j} is a m -th power. Let n=p_{1}^{e_{1}}\cdot\ldots\cdot p_{t}^{e_{t}} , then n^{j}=p_{1}^{e_{1}j}\cdot\ldots\cdot p_{t}^{e_{t}j} is an m -th power. So m|je_{i} for all 1\leq i\leq t and therefore \frac{m}{\gcd(m,e_{i})}|j . Let d=\gcd(e_{1},\ldots,e_{t}) , so n is a d -th power. Then it follows that \frac{m}{\gcd(d,m)}|j , so if \gcd(d,m)=1 then m|j which is not possible. Therefore \gcd(d,m)>1 . If n=k^{d} where \gcd(d,m)>1 , then n^{\frac{m}{\gcd(d,m)}} is a m -th power. As 1\leq\frac{m}{\gcd(d,m)}\leq m-1 , we see that n^{\{\frac{m}{\gcd(d,m)}\}} is a m -product sequence starting at n and ending at n . Therefore g_{m}(n)=n . ∎ Lemma 2.4 . For every n that is not an m -th power, there is a corresponding sequence for g_{m}(n) that does not contain any m -th powers. Proof. Assume that in every corresponding sequence for g_{m}(n) , there appears an m -th power. Take one of these sequences, a_{1},\ldots,a_{t} , and note that \prod_{i=1}^{t}a_{i}=R^{m} for some R\in\mathbb{N} . Let there be s terms, a_{i} , that are m -th powers and label these b_{1},\ldots,b_{s} . Then \prod_{i=1}^{s}b_{i}=T^{m} for some T\in\mathbb{N} . (Note that n is not an m -th power so n\neq 0 . Therefore a_{i}\geq n>0 so R,T>0 .) Additionally T^{m}=\prod_{i=1}^{s}b_{i}|\prod_{i=1}^{t}a_{i}=R^{m}, so T|R and let R=kT for some k\in\mathbb{N} . Then if we remove all the terms that are m -th powers from a_{1},\ldots,a_{t} , we see that the product of the remaining terms is \frac{R^{m}}{T^{m}}=k^{m} . Each term that appears is still between n and g_{m}(n) , each integer appears less than m times and the sequence still starts with n . So the remaining terms form a corresponding sequence for g_{m}(n) and this does not contain any m -th powers. ∎ We will prove that if we have two m -product sequences that have different smallest terms and the same largest term, then we can always construct a third m -product sequence that satisfies certain properties. Lemma 2.5 . Let A:=(a_{i})_{i=1}^{t} and B:=(b_{i})_{i=1}^{t^{\prime}} be two m -product sequences satisfying a_{1}<b_{1} and a_{t}=b_{t^{\prime}} . Let 1\leq s_{1},s_{t}\leq m-1 be the number of appearances of a_{1} and a_{t} in A respectively, and 1\leq v_{t^{\prime}}\leq m-1 be the number of appearances of b_{t^{\prime}} in B . Then, there exists an m -product sequence, C=(c_{i})_{i=1}^{r} , with the following properties. 1. c_{1}=a_{1} appears s_{1} times in C and c_{r}\leq a_{t} , 2. a_{t} appears in C exactly s_{t}+v_{t^{\prime}}\mod

Read the complete text