login
Inverse of the Doudna sequence A005940.
(Formerly M0510)
34

%I M0510 #43 Aug 02 2024 04:02:32

%S 1,2,3,4,5,6,9,8,7,10,17,12,33,18,11,16,65,14,129,20,19,34,257,24,13,

%T 66,15,36,513,22,1025,32,35,130,21,28,2049,258,67,40,4097,38,8193,68,

%U 23,514,16385,48,25,26,131,132,32769,30,37,72,259,1026,65537,44,131073,2050,39,64

%N Inverse of the Doudna sequence A005940.

%C a(2^k) = 2^k. - _Robert G. Wilson v_, Feb 22 2005

%C Fixed points: A029747. - _Reinhard Zumkeller_, Aug 23 2006

%C Question: Is there a simple proof that a(c) = c would never allow an odd composite c as a solution? See also A364551. - _Antti Karttunen_, Jul 30 2023

%D J. H. Conway, personal communication.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H R. J. Mathar, <a href="/A005941/b005941.txt">Table of n, a(n) for n=1,..,5000</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F a(n) = h(g(n,1,1), 0) / 2 + 1 with h(n, m) = if n=0 then m else h(floor(n/2), 2*m + n mod 2) and g(n, i, x) = if n=1 then x else (if n mod prime(i) = 0 then g(n/prime(i), i, 2*x+1) else g(n, i+1, 2*x)). - _Reinhard Zumkeller_, Aug 23 2006

%F a(n) = 1 + A156552(n). - _Antti Karttunen_, Jun 26 2014

%p A005941 := proc(n)

%p local k ;

%p for k from 1 do

%p if A005940(k) = n then # code reuse

%p return k;

%p end if;

%p end do ;

%p end proc: # _R. J. Mathar_, Mar 06 2010

%t f[n_] := Block[{p = Partition[ Split[ Join[ IntegerDigits[n - 1, 2], {2}]], 2]}, Times @@ Flatten[ Table[q = Take[p, -i]; Prime[ Count[ Flatten[q], 0] + 1]^q[[1, 1]], {i, Length[p]}] ]]; t = Table[ f[n], {n, 10^5}]; Flatten[ Table[ Position[t, n, 1, 1], {n, 64}]] (* _Robert G. Wilson v_, Feb 22 2005 *)

%o (Scheme) (define (A005941 n) (+ 1 (A156552 n))) ;; _Antti Karttunen_, Jun 26 2014

%o (Python)

%o from sympy import primepi, factorint

%o def A005941(n): return sum((1<<primepi(p)-1)<<i for i, p in enumerate(factorint(n, multiple=True)))+1 # _Chai Wah Wu_, Mar 11 2023

%o (PARI) A005941(n) = { my(f=factor(n), p, p2=1, res=0); for(i=1, #f~, p = 1 << (primepi(f[i, 1])-1); res += (p * p2 * (2^(f[i, 2])-1)); p2 <<= f[i, 2]); (1+res) }; \\ (After _David A. Corneth_'s program for A156552) - _Antti Karttunen_, Jul 30 2023

%Y Cf. A103969. Inverse of A005940. One more than A156552.

%Y Cf. A364559 [= a(n)-n], A364557 (Möbius transform), A364558.

%Y Cf. A029747 [known positions where a(n) = n], A364560 [where a(n) <= n], A364561 [where a(n) <= n and n is odd], A364562 [where a(n) > n], A364548 [where n divides a(n)], A364549 [where odd n divides a(n)], A364550 [where a(n) divides n], A364551 [where a(n) divides n and n is odd].

%K nonn

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _Robert G. Wilson v_, Feb 22 2005

%E a(61) inserted by _R. J. Mathar_, Mar 06 2010