Problems & Puzzles: Puzzles

Puzzle 201. The arithmetic function A(n)

The following puzzle was sent by Luis Flavio Soares Nunes, from Brazil.

Let n = p1a1 . .... prar be the canonical representation of n.

We define A(n) = r . max(a1, ..., ar).

This function has a geometrical propriety. In fact, if we represent the prime factors of n in a rectangle, with the distinct pis in its base, and each column with ai primes pi , then A(n) represents the minimum area of a rectangle that comports this representation of n.

As example, let n = 23 . 52 . 76 . 114. Then, A(n) = 4 . max(3, 2, 6, 4) = 4 . 6 = 24.

Or, we can draw this rectangle:

 

.

.

7

.

.

.

7

.

.

.

7

11

2

.

7

11

2

5

7

11

2

5

7

11

 

And its area is A(n) = 4 . 6 = 24.

We also define an ordered conjunct Rk = {n Є N : A(n)=k}. We can see, by the above example, that 23 . 52 . 76 . 114 is in R24.

Questions:

  1. For any k, what are the first elements of Rk ?

If k=1, its easy to describe R1, simply because it is the ordered set of all primes,

R1 = {2, 3, 5, 7, 11, ...}. However, if k>1, it is difficult to enumerate Rk. We can prove that if k is prime, Rk = {2k, ...}. But, what is the next element ? Can we express it ?

For example, by calculation, we discover that R2 = {22, 2 . 3, 32, 2 . 5, 2 . 7, 3 . 5, ...}. But, is there a simpler manner of doing it ?

  1. Given k and M, how many elements smaller than M are in Rk?
  2. Is there, in every set Rk , 2 consecutive integers ?

For example, in R1 are 2 and 3. In R2 are 14=2 . 7 and 15=3 . 5. R3 contains 2197=133 and 2198=2 . 7 . 157, etc. Does it holds in every set Rk ?


Solution:

Phil Carmody and Joseph L. Pe sent interesting contributions to this puzzle:

Phil wrote:

1) If k is prime, the only elements of R_k are ones of the form p^k and k-almost-primes. The first element will always be 2^k. The second element will either be 3^k or nthprime(k)#

e.g.

k=2 either 9 or 6 => 6, i.e. nthprime(k)#
k=3 either 27 or 30 => 27 i.e. 3^k
k=4 either 81 or 210 => 81, and so on, 3^k

If k is a composite, then it can be split many ways, and the smallest element for each split will be the only one that can possibly be 2nd place, rather than 3^k. This smallest element will be the almost empty rectangle consisting of a tower of twos, and a single instance of each of the next smallest primes. i.e. 2^d.nthprime(k/d)#/2 for d|k More than that, in this expression you tend to want the largest number of powers of two, and certainly you never want d<(k/d). So the number of values you want to look at is quite small, and it you should be able to do it exhaustively almost instantly.

2) I can't see anything better than brute forcing it. It looks like it's non-P in k, but bounded above by something linear in M.

3) Given Heath-Brown's results on who sigma and tau can behave, I'd have to guess that every set will contain 2 consecutive numbers. I reckon it can always be done with 1*k (flat) rectangles too (i.e. k-almost primes).

Joseph wrote:

Recall that if n = p_1^a_1 * ... * p_r^a_r is the canonical prime factorization of n, then A(n) is defined as A(n) = r * max{a_1, ..., a_r}. The set R_k is defined as the set of natural numbers n satisfying A(n) = k. Let R_k(1) < R_k(2) < .... be the elements of R_k in increasing order.

Question 1. R_k(1), the first element of R_k, can be characterized as follows. As already noted in your article, R_k(1) = 2^k if k is prime. If k is not prime, then let d be a divisor of k and d' = k/d. Consider the product P(d) = 2^d' * 3 * 5 * ... * p(d), where p(d) is the d-th prime. Then R_k(1) is the smallest value taken by P(d), that is: R_k(1) = min_{d | k} 2^(k/d) * 3 * 5 * ... * p(d). More compactly, R_k(1) = min_{d | k} 2^(k/d - 1) * d#, where d# stands for d primorial, defined as the product of the first d primes.

My characterization of R_k(2), the second element of R_k, is not as neat, and depends upon having previously computed R_k(1). If k = 2, then R_k(2) = 6; and if k is an odd prime, then R_k(2) = 3^k. Now, if k is not prime, then let d be a divisor of k and d' = k/d. Consider the product P(d) = 2^d' * q_2 * q_3 * ... * q_d, where q_2 < q_3 < ... < q_d is any sequence of d-1 primes for which R_k(1) < P(d) < 3^k. (3^k is probably not the tightest bound possible here.) Then R_k(2) is the smallest value taken by P(d), that is: R_k(2) = min_{d | k, R_k(1) < P(d) < 3^k} P(d).

Here is a table of the first and second elements of R_k to illustrate the above expressions.

k first element of R_k second element of R_k
1 2 3^1
2 2^2 2^1 * 3^1
3 2^3 3^3
4 2^2 * 3^1 2^4
5 2^5 3^5
6 2^3 * 3^1 2^3 * 5^1
7 2^7 3^7
8 2^4 * 3^1 2^4 * 5^1
9 2^3 * 3^1 * 5^1 2^3 * 3^1 * 5^1
10 2^4 * 3^1 2^5 * 5^1
11 2^11 3^11
12 2^6 * 3^1 2^4 * 3^1 * 5^1
13 2^13 3^13
14 2^7 * 3^1 2^7 * 5^1

Ok, these "formulas" aren't really very practical. To enumerate R_k, it is much easier to use an inductive procedure, speeded up by a sieve method and other heuristics. The most obvious way to enumerate R_k:

Base step. To compute R_k(1), compute A(2), A(3), .... until the first t is found such that such that A(t) = k. Then R_k(1) = t. Clearly, such t exists because A(2^k) = k, so that R_k(1) <= 2^k. To speed up the search, it is easily seen that R_k(1) must be a multiple of 4 for k > 1, so that only the 2^(k-2) multiples of 4 that are <= 2^k need to be considered.

Inductive step. Suppose R_k(1) < R_k(2) < ... < R_k(s) have been found; then R_k(s+1) has to be determined. Compute A(R_k(s) + 1), A(R_k(s) + 2), .... until the first t among R_k(s) + 1, R_k(s) + 2, .... is found such that A(t) = k. Such t exists because if R_k(s) = p_1^a_1 * ... * p_r^a_r is the canonical prime factorization of R_k(s), then the number U = p_1^a_1 * ... * (p')^a_r, obtained by replacing p_r by the next prime p', is > R_k(s) and A(U) = k, so that R_k(s+1) <= U. Put R_k(s+1) = t.

This simple enumeration can be improved by incorporating a sieve method (as in the sieve of Eratosthenes). Start with the list {2, 3, ....}. Proceed as above, computing A(2), A(3), .... If A(i) = k, encircle the integer i. If A(i) is not equal to k, then underline i. In addition, if A(i) > k, then A(I) >= A(i) > k for any multiple I of i; hence, underline every i-th number in the list (corresponding to a multiple of i). Compute A(i) only for i that has not yet been encircled or underlined. The (ordered) list of encircled numbers enumerates the elements of R_k.

Here is a Mathematica program (implementing just the "obvious" method) to enumerate R_4 and print any pairs of

consecutive elements:
A[n_] := Module[{pf}, pf = Transpose[FactorInteger[n]];
Length[pf[[1]]]*Max[pf[[2]]]];
R[k_] := Module[{l, ub, i, lastval},
l = {};
ub = 10^4;
lastval = 0;
For[i = 2, i <= ub, i++,
If[A[i] == k,
l = Append[l, i];
If[i == lastval + 1,
Print[ToString[(i - 1)] <> " and " <> ToString[i] <>
" are consecutive elements"]];
lastval = i
]];
l];
R[4]

Question 3. I have verified (using the program above) that R_1, ..., R_6 have consecutive elements, but there are no consecutive elements < 10^8 in R_7. I suspect the answer to this question is "no", but I have only empirical evidence.

I asked to Phil what was his opinion on the Pe's comment to question 3, a kind of divergent of his own comment based on the Heath-Brown's work. This is what he answered (are you ready for it?)

The case R_p with p prime does seriously restrict the number of ways of finding values. R_k is contains 7th powers, and products of 7 primes, doesn't it?

19203908986158 = 2*3*13*281*337*1289*2017 precedes 19203908986159 = 79^7

The following are also consecutive powers/7-almost-primes

prime [factorization of 7-almost-prime] prime^7
power > 7-almost-prime:

191 [2, 5, 19, 127, 197, 10627, 183569] 9273284218074431
223 [2, 3, 29, 37, 491, 1709, 5076443] 27424204663190047
359 [2, 179, 211, 449, 1303, 4019, 4327] 768530557342240919
1283 [2, 29, 631, 641, 3739, 24781, 2632673] 5722510452670311609227
(after these a long list of other solutions)

power < 7-almost-prime:

457 [2, 29, 43, 229, 421, 7309, 2368871] 4163067000501310393
709 [2, 5, 29, 71, 6287, 534857, 1300727] 90058279596528053869
761 [2, 3, 71, 113, 127, 105883, 228336109] 147806181513219494921
821 [2, 3, 29, 137, 197, 631, 84847040587] 251421318647928806141
(after these a long list of other solutions)

These are just the ones <10^35. I have no reason to suspect that they thin out so much that they ever run out. I've not even thought of looking at consecutive 7-almost-primes, these would be _much much_ more common than ones that are adjacent to prime powers, such as those found above.

The work of Heath-Brown _proves_ that you will find consecutive k-almost primes for every k. So my gut feel isn't required. Every set will have consecutive terms. Full stop.

So restricting ourselves to the harder problem of prime-powers 'towers'  next to flatter arrangements...

R_8 is in some ways harder (a sparse form, and one that has a massively factorable neighbor to the power). However, there are several 'tower blocks' that work [1,1,1,1,1,1,1,1], [2,1,1,1], [2,2,1,1], [2,2,2,1], [2,2,2,2], [4,1], [4,2], [4,3], [4,4], which makes it easier.

Here are the solutions up to 10^40:

prime power < 8-almost-prime:

131 [2, 17, 7841, 19136877329] 86730203469006241
709 [2, 17, 3089, 35762192350095041] 63851320233938390193121
1231 [2, 17, 72648689, 125576624052401] 5273080767529718372423041
(after these a long list of other solutions)

prime power > 8-almost-prime:None, too make algebraic factors of p^8-1

R_9 has swings in its favor and almost nothing against its favor

347 [2, 7, 13, 19, 73, 173, 1297, 1327, 970421527] 72939918399605131977467
947 [2, 7, 11, 19, 43, 109, 277, 463, 348272974918243] 612561660047653251978446867
(after these a long list of other solutions)

R_10 also has some results, a few more that R_8, but looking similarly one-sided due to the algebraic factorization of p^10-1.

17 [2, 5, 29, 21881, 63541] 2015993900449
37 [2, 5, 61, 137, 11507920001] 4808584372417849

R_11 refused to give me a result, but searching is harder as you're looking at 50+digit numbers. It would be a drag to try to optimize the code to early-abort if it can't find enough small factors quickly, as I'm using pari/gp, and I'm not a particularly good programmer in that language. (It's 2 lines of code to find the above results in pari/gp!). So I hope that's put the R_7 problem to bed. Alas it's awakened a R_11 problem instead :-)...

No it hasn't - this just in:

6343 [2, 3, 7, 23, 151, 1409, 1607, 311323, 405989, 502608943, 31871697617] 668716170795985943898848282166258251528407

Uf!!!... Thanks Phil.

***

Frank Rubin sent the following comment (20/11/2002) regarding the same issue of the question 3:

I think that every R_k contains not just 2 consecutive integers, but longer sequences of n consecutive integers as well.  For example, R_5 contains 1042404, 1042405 and 1042406.  Sudipta Das and I found similar sequences for other values of k and n.

***

Later Rubin added a more complete table of results and comments:

I have now searched all of the integers through 2,100,000,000 for consecutive integers having the same number of prime factors.  I made two separate runs, one for distinct prime factors, like the puzzle on my website, and total prime factors, like the puzzle on your website.

The results are somewhat different from what I had expected.  There do not seem to be any sequences longer than 8 consecutive numbers having 2 distinct prime factors.  The reason for this is that, just as the primes thin out as you get larger, the numbers that can be expressed as the product of 2 primes thin out.  I think this will eventually happen with 3 primes, 4 primes, and so forth.  However, it will occur at points much greater than 2.1 billion.

With total prime factors the length of the sequences is limited by the number of factors.  With n factors there cannot be more than 2^n-1 consecutive integers.  This is because any 2^n consecutive integers will contain a multiple of 2^n, which must have more than n factors.  (The first multiple, namely 1x2^n cannot be part of a sequence of consecutive integers with n factors.  2^n is the first integer with n factors, so 2^n-1 has fewer than n factors.  The next integer with n factors will be 3x2^(n-1) so 2^n+1 also must have fewer than n factors.)

My belief is that for 4 total factors there will be sequences of 15 consecutive integers.  It is less clear if this will hold true for larger numbers of factors, for example that there will actually be sequences of 31 consecutive integers having 5 total factors.

I have attached two tables showing the smallest integer that begins a sequence of n consecutive integers with k factors.
 

Frank Rubin  Dec. 7, 2002

* Distinct prime factors

Run			       k Number of factors
Len	2	  3	     4	       5	 6	6	   7	    8	      9
---   ---   -------   --------	--------  --------  --------  -------  --------
 1:	6	 30	   210	    2310      30030     510510   9699690 223092870
 2:    14	230	   7314	  254540  11243154  965009045	    0	          0
 3:    20	644	 37960	 1042404  323567034	    0 	     0	        0
 4:    33      1308	134043	21871365	 0	    0	    0	          
 5:    54      2664	357642 129963314	 0	   0	        0	       
 6:    91      6850    1217250 830692265	 0	   0	        0	      0
 7:   141     10280    1217250	       0	 0	    0	    0	          0
 8:   141     39693   14273478	       0	 0          0	    0	          0
 9:	0     44360   44939642	       0	            0	   0 0	        0	      0
10:	0     48919   76067298	       0	            0	   0 0	        0
11:	0    218972  163459742	       0	 0	   0	        0	      0
12:	0    526095  547163235	       0	 0	   0	        0	      0
13:	0    526095 2081479430	       0	 0	   0	        0	      0
14:	0    526095	     0	        0	 0	    0	    0	          0
15:	0  17233173	     0	        0	 0	    0	    0	          0
16:	0 127890362	     0	        0	 0	    0	    0	          0


* Total prime factors

Run				   k Number of factors
Len	    2	     3		       4	  5	    6	      7 	       8	  9	   10
---	  ---  -------	 --------  --------  --------  --------  --------  --------  --------
 1:	    4	     8	       16	32	  64	    128       256	512	 1024
 2:	    9	    27	      135       944	5264	  29888     50624    203391   3290624
 3:	   33	   170	     1274     15470     33614	3145310  40909374 668363967	    0
 4:	    0	   602	     4023     57967   8706123  296299374 	0	  0	    0
 5:	    0	   602	    12122    632148 101905622	      0 	0	  0	    0
 6:	    0	   2522	  204323  14845324	   0	      0 	0	  0	    0
 7:	    0	 211673	  355923  69921004	   0	      0 	0	  0	    0
 8:	    0	     0	  3405122 888781058	   0	      0 	0	  0	    0
 9:	    0	     0	  3405122	 0	   0	      0 	0	  0	    0
10:	    0	     0	 49799889	 0         0	    0 0	        0 	  0	    	    
11:	    0	     0	202536181	 0	   0	      0 	0	  0	    0

***

Trial Brian sent a note (10/12/2002) reminding that he solved the CYF No. 8, of the Shyam Sunder Gupta's site, related to the Rubin's belief "My belief is that for 4 total factors there will be sequences of 15 consecutive integers"

***

 



Records   |  Conjectures  |  Problems  |  Puzzles