login
A292381
Base-2 expansion of a(n) encodes the steps where numbers of the form 4k+1 are encountered when map x -> A252463(x) is iterated down to 1, starting from x=n.
12
1, 2, 4, 4, 9, 8, 18, 8, 9, 18, 36, 16, 73, 36, 16, 16, 147, 18, 294, 36, 37, 72, 588, 32, 19, 146, 16, 72, 1177, 32, 2354, 32, 73, 294, 32, 36, 4709, 588, 144, 72, 9419, 74, 18838, 144, 33, 1176, 37676, 64, 39, 38, 292, 292, 75353, 32, 74, 144, 589, 2354, 150706, 64, 301413, 4708, 72, 64, 147, 146, 602826, 588, 1177, 64, 1205652, 72, 2411305, 9418, 36, 1176
OFFSET
1,2
FORMULA
a(1) = 1; for n > 1, a(n) = 2*a(A252463(n)) + [n ≡ 1 (mod 4)], where the last part of the formula is Iverson bracket, giving 1 only if n is of the form 4k+1, and 0 otherwise.
a(n) = A292371(A292384(n)).
Other identities. For n >= 1:
a(2n) = 2*a(n).
A000120(a(n)) = A292375(n).
For n >= 2, a(n) = A004754(A292385(n)).
EXAMPLE
For n = 1, the starting value (which is also the ending point) is of the form 4k+1, thus a(1) = 1*(2^0) = 1.
For n = 2, the starting value is not of the form 4k+1, but its parent, A252463(2) = 1 is, thus a(2) = 0*(2^0) + 1*(2^1) = 2.
For n = 3, the starting value is not of the form 4k+1, after which follows 2 (also not 4k+1), and then 2 -> 1, and it is only the end-point of iteration which is of the form 4k+1, thus a(3) = 0*(2^0) + 0*(2^1) + 1*(2^2) = 4.
For n = 5, the starting value is of the form 4k+1, after which follows A252463(5) = 3 (which is not), and then continuing as before as 3 -> 2 -> 1, thus a(5) = 1*(2^0) + 0*(2^1) + 0*(2^2) + 1*(2^3) = 9.
MATHEMATICA
Table[FromDigits[Reverse@ NestWhileList[Function[k, Which[k == 1, 1, EvenQ@ k, k/2, True, Times @@ Power[Which[# == 1, 1, # == 2, 1, True, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger@ k]], n, # > 1 &] /. k_ /; IntegerQ@ k :> If[Mod[k, 4] == 1, 1, 0], 2], {n, 76}] (* Michael De Vlieger, Sep 21 2017 *)
PROG
(PARI)
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1, 1]==2), f[1, 2] = 0); for (i=1, #f~, f[i, 1] = precprime(f[i, 1]-1)); factorback(f)};
A252463(n) = if(!(n%2), n/2, A064989(n));
A292381(n) = if(1==n, n, (if(1==(n%4), 1, 0)+(2*A292381(A252463(n)))));
(Scheme) (define (A292381 n) (A292371 (A292384 n)))
(Python)
from sympy.core.cache import cacheit
from sympy.ntheory.factor_ import digits
from sympy import factorint, prevprime
from operator import mul
from functools import reduce
def a292371(n):
k=digits(n, 4)[1:]
return 0 if n==0 else int("".join(['1' if i==1 else '0' for i in k]), 2)
def a064989(n):
f=factorint(n)
return 1 if n==1 else reduce(mul, [1 if i==2 else prevprime(i)**f[i] for i in f])
def a252463(n): return 1 if n==1 else n//2 if n%2==0 else a064989(n)
@cacheit
def a292384(n): return 1 if n==1 else 4*a292384(a252463(n)) + n%4
def a(n): return a292371(a292384(n))
print([a(n) for n in range(1, 111)]) # Indranil Ghosh, Sep 21 2017
KEYWORD
nonn,base
AUTHOR
Antti Karttunen, Sep 15 2017
STATUS
approved