A246370 -id:A246370 - cp's OEIS frontend

A135141 a(1)=1, a(p_n)=2a(n), a(c_n)=2a(n)+1, where p_n = n-th prime, c_n = n-th composite number.

1, 2, 4, 3, 8, 5, 6, 9, 7, 17, 16, 11, 10, 13, 19, 15, 12, 35, 18, 33, 23, 21, 14, 27, 39, 31, 25, 71, 34, 37, 32, 67, 47, 43, 29, 55, 22, 79, 63, 51, 20, 143, 26, 69, 75, 65, 38, 135, 95, 87, 59, 111, 30, 45, 159, 127, 103, 41, 24, 287, 70, 53, 139, 151, 131, 77, 36, 271, 191

Offset: 1

Katarzyna Matylla, Feb 13 2008

A permutation of the positive integers, related to A078442.
a(p) is even when p is prime and is divisible by 2^(prime order of p).
From Robert G. Wilson v, Feb 16 2008: (Start)
What is the length of the cycle containing 10? Is it infinite? The cycle begins 10, 17, 12, 11, 16, 15, 19, 18, 35, 29, 34, 43, 26, 31, 32, 67, 36, 55, 159, 1055, 441, 563, 100, 447, 7935, 274726911, 1013992070762272391167, ... Implementation in Mmca: NestList[a(AT)# &, 10, 26] Furthermore, it appears that any non-single-digit number has an infinite cycle.
Records: 1, 2, 4, 8, 9, 17, 19, 35, 39, 71, 79, 143, 159, 287, 319, 575, 639, 1151, 1279, 2303, 2559, 4607, 5119, 9215, 10239, 18431, 20479, 36863, 40959, 73727, 81919, 147455, 163839, 294911, 327679, 589823, 655359, ..., . (End)

			a(20) = 33 = 2*16 + 1 because 20 is 11th composite and a(11)=16. Or, a(20)=33=100001(bin). In other words it is a composite number, its index is a prime number, whose index is a prime....

Robert G. Wilson v, Table of n, a(n) for n = 1..10000
Antti Karttunen, Entanglement Permutations, 2016-2017
Index entries for sequences computed from indices in prime factorization
Index entries for sequences that are permutations of the natural numbers

Cf. A000720, A007814, A010051, A026238, A078442.
Cf. A246346, A246347 (record positions and values).
Cf. A227413 (inverse).
Cf. A071574, A245701, A245702, A245703, A245704, A246377, A236854, A237427 for related and similar permutations.

import Data.List (genericIndex)
a135141 n = genericIndex a135141_list (n-1)
a135141_list = 1 : map f [2..] where
   f x | iprime == 0 = 2 * (a135141 $ a066246 x) + 1
       | otherwise   = 2 * (a135141 iprime)
       where iprime = a049084 x
-- Reinhard Zumkeller, Jan 29 2014

a[1] = 1; a[n_] := If[PrimeQ@n, 2*a[PrimePi[n]], 2*a[n - 1 - PrimePi@n] + 1]; Array[a, 69] (* Robert G. Wilson v, Feb 16 2008 *)

/* Let pc = prime count (which prime it is), cc = composite count: */
pc[1]:0;
cc[1]:0;
pc[2]:1;
cc[4]:1;
pc[n]:=if primep(n) then 1+pc[prev_prime(n)] else 0;
cc[n]:=if primep(n) then 0 else if primep(n-1) then 1+cc[n-2] else 1+cc[n-1];
a[1]:1;
a[n]:=if primep(n) then 2*a[pc[n]] else 1+2*a[cc[n]];

A135141(n) = if(1==n, 1, if(isprime(n), 2*A135141(primepi(n)), 1+(2*A135141(n-primepi(n)-1)))); \\ Antti Karttunen, Dec 09 2019

from sympy import isprime, primepi
def a(n): return 1 if n==1 else 2*a(primepi(n)) if isprime(n) else 2*a(n - 1 - primepi(n)) + 1 # Indranil Ghosh, Jun 11 2017, after Mathematica code

a(n) = 2*A135141((A049084(n))*chip + A066246(n)*(1-chip)) + 1 - chip, where chip = A010051(n). - Reinhard Zumkeller, Jan 29 2014
From Antti Karttunen, Dec 09 2019: (Start)
A007814(a(n)) = A078442(n).
A070939(a(n)) = A246348(n).
A080791(a(n)) = A246370(n).
A054429(a(n)) = A246377(n).
A245702(a(n)) = A245703(n).
a(A245704(n)) = A245701(n). (End)

A246377 Permutation of natural numbers: a(1) = 1, a(p_n) = 2a(n)+1, a(c_n) = 2a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n).

Original entry on oeis.org

1, 3, 7, 2, 15, 6, 5, 14, 4, 30, 31, 12, 13, 10, 28, 8, 11, 60, 29, 62, 24, 26, 9, 20, 56, 16, 22, 120, 61, 58, 63, 124, 48, 52, 18, 40, 25, 112, 32, 44, 27, 240, 21, 122, 116, 126, 57, 248, 96, 104, 36, 80, 17, 50, 224, 64, 88, 54, 23, 480, 121, 42, 244, 232, 252, 114, 59, 496, 192, 208, 125, 72, 49, 160, 34, 100

Offset: 1

Antti Karttunen, Aug 27 2014

nonn

This permutation is otherwise like Katarzyna Matylla's A135141, except that the role of even and odd numbers (or alternatively: primes and composites) has been swapped.
Because 2 is the only even prime, it implies that, apart from a(2)=3, odd numbers occur in odd positions only (along with many even numbers that also occur in odd positions).
This also implies that for each odd composite (A071904) there exists a separate infinite cycle in this permutation, apart from 9 and 15 which are in the same infinite cycle: (..., 23, 9, 4, 2, 3, 7, 5, 15, 28, 120, 82, 46, ...).

Antti Karttunen, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers

Inverse: A246378.
Cf. A000720, A010051, A065855, A071904, A246348, A246369, A246370.
Other related or similar permutations: A135141, A054429, A246201, A245703, A246376, A246379, A243071, A246681, A236854.
Differs from A237427 for the first time at n=19, where a(19) = 29, while A237427(19) = 62.

a(1) = 1, and for n > 1, if A010051(n) = 1 [i.e. when n is a prime], a(n)  = 1+(2*a(A000720(n))), otherwise a(n) = 2*a(A065855(n)).
As a composition of related permutations:
a(n) = A054429(A135141(n)).
a(n) = A135141(A236854(n)).
a(n) = A246376(A246379(n)).
a(n) = A246201(A245703(n)).
a(n) = A243071(A246681(n)). [For n >= 1].
Other identities.
For all n > 1 the following holds:
A000035(a(n)) = A010051(n). [Maps primes to odd numbers > 1, and composites to even numbers, in some order. Permutations A246379 & A246681 have the same property].

A246348 a(1)=1, a(p_n) = 1 + a(n), a(c_n) = 1 + a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n); Also binary width of terms of A135141.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 3, 4, 3, 5, 5, 4, 4, 4, 5, 4, 4, 6, 5, 6, 5, 5, 4, 5, 6, 5, 5, 7, 6, 6, 6, 7, 6, 6, 5, 6, 5, 7, 6, 6, 5, 8, 5, 7, 7, 7, 6, 8, 7, 7, 6, 7, 5, 6, 8, 7, 7, 6, 5, 9, 7, 6, 8, 8, 8, 7, 6, 9, 8, 8, 7, 7, 6, 8, 6, 7, 9, 8, 6, 8, 7, 6, 5, 10, 8, 7, 9, 9, 6, 9, 8, 7, 10

Offset: 1

Antti Karttunen, Aug 27 2014

nonn

If n = 1, the result is 1, otherwise, if n is prime, compute the result for that prime's index (A000720 or A049084) and add one, and if n is composite, compute the result for that composite's index (A065855) and add one.

a(n) tells how many calls (including the toplevel call) are required to compute A135141(n) or A246377(n) with a simple (nonmemoized) recursive algorithm as employed for example by Robert G. Wilson v's Mathematica-program of Feb 16 2008 in A135141 or Antti Karttunen's Scheme-proram in A246377.

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

Cf. A000040, A002808, A000720, A065855, A070939, A135141, A246346, A246347, A246369, A246370, A246377.

\\ Compute the b-files for both the positions of records (A246346) and their values (A246347) and also for A246348 (somewhat naively):
default(primelimit, (2^31)+(2^30));
A070939 = n->#binary(n)+!n \\ From M. F. Hasler
A135141(n) = if(1==n, 1, if(isprime(n), 2*A135141(primepi(n)), 1+(2*A135141(n-primepi(n)-1))));
A246348(n) = A070939(A135141(n));
prevmax = -1; i = 0; for(n=1, 123456, if((k=A135141(n)) > prevmax, prevmax = k; i++; write("b246346.txt", i, " ", n); write("b246347.txt", i, " ", k)); write("b246348.txt", n, " ", A246348(n)));
(Scheme, two versions, second being a direct recurrence employing memoizing definec-macro from Antti Karttunen's IntSeq-library)
(define (A246348 n) (A070939 (A135141 n)))
(definec (A246348 n) (cond ((= 1 n) 1) ((= 1 (A010051 n)) (+ 1 (A246348 (A000720 n)))) (else (+ 1 (A246348 (A065855 n))))))

a(1) = 1, and for n >= 1, if A010051(n)=1 [that is, when n is prime], a(n) = 1 + a(A000720(n)), otherwise a(n) = 1 + a(A065855(n)). [A000720(n) and A065855(n) tell the number of primes, and respectively, composites <= n].
a(n) = A246369(n) + A246370(n).
a(n) = A070939(A135141(n)) = 1 + floor(log_2(A135141(n))). [Sequence gives also the binary width of terms of A135141].
a(n) = A070939(A246377(n)). [Also for 0/1-swapped version of that sequence].

A252736 a(1) = a(2) = 0; for n > 2: a(2n) = 1 + a(n), a(2n+1) = a(A064989(2n+1)).

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 0, 2, 0, 1, 1, 3, 0, 2, 0, 2, 1, 1, 0, 3, 1, 1, 2, 2, 0, 2, 0, 4, 1, 1, 1, 3, 0, 1, 1, 3, 0, 2, 0, 2, 2, 1, 0, 4, 1, 2, 1, 2, 0, 3, 1, 3, 1, 1, 0, 3, 0, 1, 2, 5, 1, 2, 0, 2, 1, 2, 0, 4, 0, 1, 2, 2, 1, 2, 0, 4, 3, 1, 0, 3, 1, 1, 1, 3, 0, 3, 1, 2, 1, 1, 1, 5, 0, 2, 2, 3, 0, 2, 0, 3, 2, 1, 0, 4, 0, 2, 1, 4, 0, 2, 1, 2, 2, 1, 1, 4, 1, 1, 1, 2, 2, 3, 0, 6

Offset: 1

Antti Karttunen, Dec 21 2014

nonn

Consider the binary tree illustrated in A005940: If we start from any n, computing successive iterations of A252463 until 1 is reached (i.e., we are traversing level by level towards the root of the tree, starting from that vertex of the tree where n is located), a(n) gives the number of even numbers > 2 encountered on the path (i.e., excluding the 2 from the count but including the starting n if it was even).

The number of pairs in any factorization tree of n. For example, a possible factorization tree of 12 is 12 -> (4*3) -> (2*2)*3. There are 2 pairs in this factor tree: (4*3) and (2*2). Thus, a(12) - 1 = 3 - 1 = 2. - Melvin Peralta, Aug 29 2016

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

Essentially one less than A001222.
Cf. A000120, A005940, A064989, A080791, A156552, A243071, A252464, A252735.
Cf. also A246370.

a[1] = a[2] = 0; a[n_] := a[n] = If[EvenQ@ n, 1 + a[n/2], a[Times @@ Power[Which[# == 1, 1, # == 2, 1, True, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger@ n]]; Array[a, 120] (* Michael De Vlieger, Aug 30 2016 *)

a(1) = a(2) = 0; for n > 2: a(2n) = 1 + a(n), a(2n+1) =  a(A064989(2n+1)).
a(n) = A080791(A243071(n)). [Number of nonleading 0-bits in A243071(n).]
Other identities. For all n >= 2:
a(n) = A000120(A156552(n)) - 1. [One less than the binary weight of A156552(n).]
a(n) = A252464(n) - A252735(n) - 1.
a(n) = A001222(n) - 1.

A246369 a(1)=0, a(p_n) = a(n), a(c_n) = 1 + a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n); Also one less than the binary weight of terms of A135141.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 1, 1, 2, 1, 0, 2, 1, 2, 2, 3, 1, 2, 1, 1, 3, 2, 2, 3, 3, 4, 2, 3, 1, 2, 0, 2, 4, 3, 3, 4, 2, 4, 5, 3, 1, 4, 2, 2, 3, 1, 2, 3, 5, 4, 4, 5, 3, 3, 5, 6, 4, 2, 1, 5, 2, 3, 3, 4, 2, 3, 1, 4, 6, 5, 1, 5, 3, 6, 4, 4, 6, 7, 2, 5, 3, 2, 2, 6, 3, 4, 4, 5, 3, 3, 4, 2, 5, 7, 6, 2, 3, 6, 4, 7, 4, 5, 2, 5, 7, 8, 3, 3, 1, 6, 4, 3, 2, 3, 7, 4, 5, 5, 6, 4

Offset: 1

Antti Karttunen, Aug 27 2014

nonn

Consider the following algorithm:
Start:
If n is 1, we have finished,
Otherwise:
If n is a prime, replace it with its index among the primes, n <- A000720(n), and go back to the start.
Otherwise, if n is a composite, replace it with its index among the composites, n <- A065855(n), and go back to the start.
At some point, the process is guaranteed to reach the number 1 at which point we stop.
a(n) tells how many times a composite number was encountered in the process, before 1 was reached. This count includes also +1 for the cases where the initial n was composite at the beginning.

			Consider n=30. It is the 19th composite number in A002808: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, ...
Thus we consider next n=19, which is the 8th prime in A000040: 2, 3, 5, 7, 11, 13, 17, 19, ...
So we proceed with n=8, which is the 3rd composite number, and then with n=3, which is the 2nd prime, and then with n=2 which is the 1st prime, and we have finished.
All in all, it took us 5 steps (A246348(30) = 6 = 5+1) to reach 1, and on the journey, we encountered two composites, 30 and 8, thus a(30) = 2.

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

Cf. A000040, A002808, A000120, A000720, A065855, A135141, A246348, A246370, A246377.

a(1) = 1, and for n >= 1, if A010051(n) = 1 [that is, when n is prime], a(n) = a(A000720(n)), otherwise a(n) = 1 + a(A065855(n)). [A000720(n) and A065855(n) tell the number of primes, and respectively, composites <= n].
a(n) = A000120(A135141(n)) - 1. [a(n) is also one less than the Hamming weight (number of 1-bits) of the n-th term of A135141].
a(n) = A080791(A246377(n)). [Respectively, the number of 0-bits for 0/1-swapped version of that sequence].
a(n) = A246348(n) - A246370(n) - 1.

cp's OEIS Frontend

A135141 a(1)=1, a(p_n)=2*a(n), a(c_n)=2*a(n)+1, where p_n = n-th prime, c_n = n-th composite number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Maxima

PARI

Python

Formula

A246377 Permutation of natural numbers: a(1) = 1, a(p_n) = 2*a(n)+1, a(c_n) = 2*a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A246348 a(1)=1, a(p_n) = 1 + a(n), a(c_n) = 1 + a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n); Also binary width of terms of A135141.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A252736 a(1) = a(2) = 0; for n > 2: a(2n) = 1 + a(n), a(2n+1) = a(A064989(2n+1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A246369 a(1)=0, a(p_n) = a(n), a(c_n) = 1 + a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n); Also one less than the binary weight of terms of A135141.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A135141 a(1)=1, a(p_n)=2a(n), a(c_n)=2a(n)+1, where p_n = n-th prime, c_n = n-th composite number.

A246377 Permutation of natural numbers: a(1) = 1, a(p_n) = 2a(n)+1, a(c_n) = 2a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n).