A246272 Starting from n, the number of iterations of A003961 needed before the result has only prime factors of the form 4k+1 (a(1) = 0). [Where A003961(n) shifts the prime factorization of n one step towards larger primes].

0, 2, 1, 2, 0, 5, 2, 2, 1, 9, 1, 5, 0, 2, 4, 2, 0, 5, 2, 9, 8, 2, 1, 5, 0, 6, 1, 2, 0, 23, 1, 2, 1, 5, 3, 5, 0, 2, 1, 9, 0, 49, 2, 2, 4, 9, 1, 5, 2, 9, 5, 6, 0, 5, 7, 2, 4, 2, 1, 23, 0, 2, 8, 2, 0, 5, 2, 5, 1, 9, 1, 5, 0, 6, 4, 2, 2, 23, 2, 9, 1, 5, 1, 49, 0, 2, 8, 2, 0, 23, 6, 9, 1, 6, 4, 5, 0, 2, 1, 9

Offset: 1

Author

Antti Karttunen, Aug 21 2014

Keywords

• nonn

Comments

Among the first 10000 terms, of which 4371 are primes, there are 92 distinct values in total (of which 23 are primes), the most common of them being: 1600 x 2, 1324 x 5, 1131 x 1, 1074 x 0, 571 x 4, 557 x 6, 538 x 9, 409 x 23, 404 x 3, 378 x 11, 211 x 8, 197 x 15, 131 x 12, 130 x 24, 128 x 49, 119 x 10, 95 x 7, 95 x 76, 92 x 22, 80 x 32, 70 x 14, 53 x 20, 47 x 77, 44 x 28, 29 x 17, 27 x 58, 24 x 21, 24 x 64, 23 x 13, 22 x 31, 22 x 39, 20 x 25, 19 x 48.

In contrast to A246271, here it holds that a(u) <= a(u*v) >= a(v) for any u, v. This follows because a number n has reached the "state of 4k+1 purity" (meaning that A065338(n) = 1) only if all its possible divisors have reached it as well.

This explains why for example 23 seems to be so common value. The reason is, that it occurs for the first time as a(30), and 30, being the third primorial is a product of three commonest primes: 30 = 2*3*5, thus for any n which is a multiple of 30, a(n) >= 23. Similarly a(42) = 49, a(84) = 49, a(126) = 49, so any number k which has 2, 3 and 7 as its prime factors must have a(k) >= 49.

Examples

			Consider n = 6 = 2*3 = p_1 * p_2. Five is the least number of iterations of A003961(n) (which increments by one the prime indices of prime factorization of n), before both primes are of the form 4k+1:
  p_2 = 3, p_3 = 5 (4k+3 & 4k+1),
  p_3 = 5, p_4 = 7 (4k+1 & 4k+3),
  p_4 = 7, p_5 = 11 (4k+3 & 4k+3),
  p_5 = 11, p_6 = 13 (4k+3 & 4k+1),
  p_6 = 13, p_7 = 17 (4k+1 & 4k+1),
thus a(6) = 5.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10001

Crossrefs

A004613 gives the positions of zeros.

A246349 gives the positions of records and A246350 the corresponding values.

Cf. A003961, A065338, A246269, A246270, A246271, A246277.

Programs

PARI

default(primelimit, 2^22)
A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Using code of Michel Marcus
A065338(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = (f[i, 1]%4)); factorback(f);
A246272(n) = {my(i); i=0; while((A065338(n)!=1), i++; n = A003961(n)); i};
for(n=1, 10001, write("b246272.txt", n, " ", A246272(n)));

Scheme

(define (A246272 n) (let loop ((i 0) (n n)) (if (= 1 (A065338 n)) i (loop (+ i 1) (A003961 n)))))

Scheme

;; Requires memoizing definec-macro.
(definec (A246272 n) (if (= 1 (A065338 n)) 0 (+ 1 (A246272 (A003961 n)))))

Formula

If A065338(n) = 1, a(n) = 0, otherwise 1 + a(A003961(n)).

Other identities:

a(n) = a(A007947(n)) for all n. [Duplicate prime factors have no effect on the result].