A245605 -id:A245605 - cp's OEIS frontend

A064989 Multiplicative with a(2^e) = 1 and a(p^e) = prevprime(p)^e for odd primes p.

1, 1, 2, 1, 3, 2, 5, 1, 4, 3, 7, 2, 11, 5, 6, 1, 13, 4, 17, 3, 10, 7, 19, 2, 9, 11, 8, 5, 23, 6, 29, 1, 14, 13, 15, 4, 31, 17, 22, 3, 37, 10, 41, 7, 12, 19, 43, 2, 25, 9, 26, 11, 47, 8, 21, 5, 34, 23, 53, 6, 59, 29, 20, 1, 33, 14, 61, 13, 38, 15, 67, 4, 71, 31, 18, 17, 35, 22, 73, 3, 16

Offset: 1

Vladeta Jovovic, Oct 30 2001

From Antti Karttunen, May 12 2014: (Start)
a(A003961(n)) = n for all n. [This is a left inverse function for the injection A003961.]
Bisections are A064216 (the terms at odd indices) and A064989 itself (the terms at even indices), i.e., a(2n) = a(n) for all n.
(End)
From Antti Karttunen, Dec 18-21 2014: (Start)
When n represents an unordered integer partition via the indices of primes present in its prime factorization (for n >= 2, n corresponds to the partition given as the n-th row of A112798) this operation subtracts one from each part. If n is of the form 2^k (a partition having just k 1's as its parts) the result is an empty partition (which is encoded by 1, having an "empty" factorization).
For all odd numbers n >= 3, a(n) tells which number is located immediately above n in square array A246278. Cf. also A246277.
(End)
Alternatively, if numbers are represented as the multiset of indices of prime factors with multiplicity, this operation subtracts 1 from each element and discards the 0's. - M. F. Hasler, Dec 29 2014

			a(20) = a(2^2*5) = a(2^2)*a(5) = prevprime(5) = 3.

Harry J. Smith (first 1000 terms) & Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A064216 (odd bisection), A003961 (inverse), A151799.
Cf. A000040, A008578, A027746, A032742, A049084, A052126, A055396, A061395, A112798, A249817, A249818.
Other sequences whose definition involve or are some other way related with this sequence: A105560, A108951, A118306, A122111, A156552, A163511, A200746, A241909, A243070, A243071, A243072, A243073, A244319, A245605, A245607, A246165, A246266, A246268, A246277, A246278, A246361, A246362, A246371, A246372, A246373, A246374, A246376, A246380, A246675, A246682, A249745, A250470.
Similar prime-shifts towards smaller numbers: A252461, A252462, A252463.

a064989 1 = 1
a064989 n = product $ map (a008578 . a049084) $ a027746_row n
-- Reinhard Zumkeller, Apr 09 2012
(MIT/GNU Scheme, with Aubrey Jaffer's SLIB Scheme library)
(require 'factor)
(define (A064989 n) (if (= 1 n) n (apply * (map (lambda (k) (if (zero? k) 1 (A000040 k))) (map -1+ (map A049084 (factor n)))))))
;; Antti Karttunen, May 12 2014
(definec (A064989 n) (if (= 1 n) n (* (A008578 (A055396 n)) (A064989 (A032742 n))))) ;; One based on given recurrence and utilizing memoizing definec-macro.
(definec (A064989 n) (cond ((= 1 n) n) ((even? n) (A064989 (/ n 2))) (else (A163511 (/ (- (A243071 n) 1) 2))))) ;; Corresponds to one of the alternative formulas, but is very unpractical way to compute this sequence. - Antti Karttunen, Dec 18 2014

q:= proc(p) prevprime(p) end proc: q(2):= 1:
[seq(mul(q(f[1])^f[2], f = ifactors(n)[2]), n = 1 .. 1000)]; # Robert Israel, Dec 21 2014

Table[Times @@ Power[Which[# == 1, 1, # == 2, 1, True, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger@ n, {n, 81}] (* Michael De Vlieger, Jan 04 2016 *)

{ for (n=1, 1000, f=factor(n)~; a=1; j=1; if (n>1 && f[1, 1]==2, j=2); for (i=j, length(f), a*=precprime(f[1, i] - 1)^f[2, i]); write("b064989.txt", n, " ", a) ) } \\ Harry J. Smith, Oct 02 2009

a(n) = {my(f = factor(n)); for (i=1, #f~, if ((p=f[i,1]) % 2, f[i,1] = precprime(p-1), f[i,1] = 1);); factorback(f);} \\ Michel Marcus, Dec 18 2014

A064989(n)=factorback(Mat(apply(t->[max(precprime(t[1]-1),1),t[2]],Vec(factor(n)~))~)) \\ M. F. Hasler, Dec 29 2014

from sympy import factorint, prevprime
from operator import mul
from functools import reduce
def a(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])
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 15 2017

from math import prod
from sympy import prevprime, factorint
def A064989(n): return prod(prevprime(p)**e for p, e in  factorint(n>>(~n&n-1).bit_length()).items()) # Chai Wah Wu, Jan 05 2023

From Antti Karttunen, Dec 18 2014: (Start)
If n = product A000040(k)^e(k) then a(n) = product A008578(k)^e(k) [where A000040(n) gives the n-th prime, and A008578(n) gives 1 for 1 and otherwise the (n-1)-th prime].
a(1) = 1; for n > 1, a(n) = A008578(A055396(n)) * a(A032742(n)). [Above formula represented as a recurrence. Cf. A252461.]
a(1) = 1; for n > 1, a(n) = A008578(A061395(n)) * a(A052126(n)). [Compare to the formula of A252462.]
This prime-shift operation is used in the definitions of many other sequences, thus it can be expressed in many alternative ways:
a(n) = A200746(n) / n.
a(n) = A242424(n) / A105560(n).
a(n) = A122111(A122111(n)/A105560(n)) = A122111(A052126(A122111(n))). [In A112798-partition context: conjugate, remove the largest part (the largest prime factor), and conjugate again.]
a(1) = 1; for n > 1, a(2n) = a(n), a(2n+1) = A163511((A243071(2n+1)-1) / 2).
a(n) = A249818(A250470(A249817(n))). [A250470 is an analogous operation for "going one step up" in the square array A083221 (A083140).]
(End)
Product_{k=1..n} a(k) = n! / A307035(n). - Vaclav Kotesovec, Mar 21 2019
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} ((p^2-p)/(p^2-q(p))) = 0.220703928... , where q(p) = prevprime(p) (A151799) if p > 2 and q(2) = 1. - Amiram Eldar, Nov 18 2022

A163511 a(0)=1. a(n) = p(A000120(n)) * Product_{m=1..A000120(n)} p(m)^A163510(n,m), where p(m) is the m-th prime.

Original entry on oeis.org

1, 2, 4, 3, 8, 9, 6, 5, 16, 27, 18, 25, 12, 15, 10, 7, 32, 81, 54, 125, 36, 75, 50, 49, 24, 45, 30, 35, 20, 21, 14, 11, 64, 243, 162, 625, 108, 375, 250, 343, 72, 225, 150, 245, 100, 147, 98, 121, 48, 135, 90, 175, 60, 105, 70, 77, 40, 63, 42, 55, 28, 33, 22, 13, 128

Offset: 0

Leroy Quet, Jul 29 2009

This is a permutation of the positive integers.
From Antti Karttunen, Jun 20 2014: (Start)
Note the indexing: the domain starts from 0, while the range excludes zero, thus this is neither a bijection on the set of nonnegative integers nor on the set of positive natural numbers, but a bijection from the former set to the latter.
Apart from that discrepancy, this could be viewed as yet another "entanglement permutation" where the two complementary pairs to be interwoven together are even and odd numbers (A005843/A005408) which are entangled with the complementary pair even numbers (taken straight) and odd numbers in the order they appear in A003961: (A005843/A003961). See also A246375 which has almost the same recurrence.
Note how the even bisection halved gives the same sequence back. (For a(0)=1, take ceiling of 1/2).
(End)
From Antti Karttunen, Dec 30 2017: (Start)
This irregular table can be represented as a binary tree. Each child to the left is obtained by doubling the parent, and each child to the right is obtained by applying A003961 to the parent:
                                     1
                                     |
                  ...................2...................
                 4                                       3
       8......../ \........9                   6......../ \........5
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
  16       27         18       25         12       15         10       7
32  81   54  125    36  75   50  49     24  45   30  35     20  21   14 11
etc.
Sequence A005940 is obtained by scanning the same tree level by level in mirror image fashion. Also in binary trees A253563 and A253565 the terms on level of the tree are some permutation of the terms present on the level n of this tree. A252464(n) gives the distance of n from 1 in all these trees, and A252463 gives the parent of the node containing n.
A252737(n) gives the sum and A252738(n) the product of terms on row n (where 1 is on row 0, 1 on row 1, 3 and 4 on row 2, etc.). A252745(n) gives the number of nodes on level n whose left child is smaller than the right child, and A252744(n) is an indicator function for those nodes.
(End)
Note that the idea behind maps like this (and the mirror image A005940) admits also using alternative orderings of primes, not just standard magnitude-wise ordering (A000040). For example, A332214 is a similar sequence but with primes rearranged as in A332211, and A332817 is obtained when primes are rearranged as in A108546. - Antti Karttunen, Mar 11 2020
From Lorenzo Sauras Altuzarra, Nov 28 2020: (Start)
This sequence is generated from A228351 by applying the following procedure: 1) eliminate the compositions that end in one unless the first one, 2) subtract one unit from every component, 3) replace every tuple [t_1, ..., t_r] by Product_{k=1..r} A000040(k)^(t_k) (see the examples).
Is it true that a(n) = A337909(n+1) if and only if a(n+1) is not a term of A161992?
Does this permutation have any other cycle apart from (1), (2) and (6, 9, 16, 7)? (End)
From Antti Karttunen, Jul 25 2023: (Start)
(In the above question, it is assumed that the starting offset would be 1 instead of 0).
Questions:
Does a(n) = 1+A054429(n) hold only when n is of the form 2^k times 1, 3 or 7, i.e., one of the terms of A029748?
It seems that A007283 gives all fixed points of map n -> a(n), like A335431 seems to give all fixed points of map n -> A332214(n). Is there a general rule for mappings like these that the fixed points (if they exist) must be of the form 2^k times a certain kind of prime, i.e., that any odd composite (times 2^k) can certainly be excluded? See also note in A029747.
(End)
If the conjecture given in A364297 holds, then it implies the above conjecture about A007283. See also A364963. - Antti Karttunen, Sep 06 2023
Conjecture: a(n^k) is never of the form x^k, for any integers n > 0, k > 1, x >= 1. This holds at least for squares, cubes, seventh and eleventh powers (see A365808, A365801, A366287 and A366391). - Antti Karttunen, Sep 24 2023, Oct 10 2023.
See A365805 for why the above holds for any n^k, with k > 1. - Antti Karttunen, Nov 23 2023

			For n=3, whose binary representation is "11", we have A000120(3)=2, with A163510(3,1) = A163510(3,2) = 0, thus a(3) = p(2) * p(1)^0 * p(2)^0 = 3*1*1 = 3.
For n=9, "1001" in binary, we have A000120(9)=2, with A163510(9,1) = 0 and A163510(9,2) = 2, thus a(9) = p(2) * p(1)^0 * p(2)^2 = 3*1*9 = 27.
For n=10, "1010" in binary, we have A000120(10)=2, with A163510(10,1) = 1 and A163510(10,2) = 1, thus a(10) = p(2) * p(1)^1 * p(2)^1 = 3*2*3 = 18.
For n=15, "1111" in binary, we have A000120(15)=4, with A163510(15,1) = A163510(15,2) = A163510(15,3) = A163510(15,4) = 0, thus a(15) = p(4) * p(1)^0 * p(2)^0 * p(3)^0 * p(4)^0 = 7*1*1*1*1 = 7.
[1], [2], [1,1], [3], [1,2], [2,1] ... -> [1], [2], [3], [1,2], ... -> [0], [1], [2], [0,1], ... -> 2^0, 2^1, 2^2, 2^0*3^1, ... = 1, 2, 4, 3, ... - _Lorenzo Sauras Altuzarra_, Nov 28 2020

Inverse: A243071.
Cf. A000040, A000120, A000225, A000788, A003961, A007814, A054429, A055396, A064216, A135523, A161992, A163510, A245605, A245612, A246375, A246378, A246681, A161511, A228351, A243499, A243503, A243504, A269854, A280873, A285727, A290251, A293437, A337909.
Cf. A007283 (known positions where a(n)=n), A029747, A029748, A364255 [= gcd(n,a(n))], A364258 [= a(n)-n], A364287 (where a(n) < n), A364292 (where a(n) <= n), A364494 (where n|a(n)), A364496 (where a(n)|n), A364963, A364297.
Cf. A365808 (positions of squares), A365801 (of cubes), A365802 (of fifth powers), A365805 [= A052409(a(n))], A366287, A366391.
Cf. A005940, A332214, A332817, A366275 (variants).

f[n_] := Reverse@ Map[Ceiling[(Length@ # - 1)/2] &, DeleteCases[Split@ Join[Riffle[IntegerDigits[n, 2], 0], {0}], {k__} /; k == 1]]; {1}~Join~
Table[Function[t, Prime[t] Product[Prime[m]^(f[n][[m]]), {m, t}]][DigitCount[n, 2, 1]], {n, 120}] (* Michael De Vlieger, Jul 25 2016 *)

from sympy import prime
def A163511(n):
    if n:
        k, c, m = n, 0, 1
        while k:
            c += 1
            m *= prime(c)**(s:=(~k&k-1).bit_length())
            k >>= s+1
        return m*prime(c)
    return 1 # Chai Wah Wu, Jul 17 2023

For n >= 1, a(2n) is even, a(2n+1) is odd. a(2^k) = 2^(k+1), for all k >= 0.
From Antti Karttunen, Jun 20 2014: (Start)
a(0) = 1, a(1) = 2, a(2n) = 2*a(n), a(2n+1) = A003961(a(n)).
As a more general observation about the parity, we have:
For n >= 1, A007814(a(n)) = A135523(n) = A007814(n) + A209229(n). [This permutation preserves the 2-adic valuation of n, except when n is a power of two, in which cases that value is incremented by one.]
For n >= 1, A055396(a(n)) = A091090(n) = A007814(n+1) + 1 - A036987(n).
For n >= 1, a(A000225(n)) = A000040(n).
(End)
From Antti Karttunen, Oct 11 2014: (Start)
As a composition of related permutations:
a(n) = A005940(1+A054429(n)).
a(n) = A064216(A245612(n))
a(n) = A246681(A246378(n)).
Also, for all n >= 0, it holds that:
A161511(n) = A243503(a(n)).
A243499(n) = A243504(a(n)).
(End)
More linking identities from Antti Karttunen, Dec 30 2017: (Start)
A046523(a(n)) = A278531(n). [See also A286531.]
A278224(a(n)) = A285713(n). [Another filter-sequence.]
A048675(a(n)) = A135529(n) seems to hold for n >= 1.
A250245(a(n)) = A252755(n).
A252742(a(n)) = A252744(n).
A245611(a(n)) = A253891(n).
A249824(a(n)) = A275716(n).
A292263(a(n)) = A292264(n). [A292944(n) + A292264(n) = n.]
--
A292383(a(n)) = A292274(n).
A292385(a(n)) = A292271(n). [A292271(n) +  A292274(n) = n.]
--
A292941(a(n)) = A292942(n).
A292943(a(n)) = A292944(n).
A292945(a(n)) = A292946(n). [A292942(n) + A292944(n) + A292946(n) = n.]
--
A292253(a(n)) = A292254(n).
A292255(a(n)) = A292256(n). [A292944(n) + A292254(n) + A292256(n) = n.]
--
A279339(a(n)) = A279342(n).
a(A071574(n)) = A269847(n).
a(A279341(n)) = A279338(n).
a(A252756(n)) = A250246(n).
(1+A008836(a(n)))/2 = A059448(n).
(End)
From Antti Karttunen, Jul 26 2023: (Start)
For all n >= 0, a(A007283(n)) = A007283(n).
A001222(a(n)) = A290251(n).
(End)

More terms computed and examples added by Antti Karttunen, Jun 20 2014

A048673 Permutation of natural numbers: a(n) = (A003961(n)+1) / 2 [where A003961(n) shifts the prime factorization of n one step towards larger primes].

Original entry on oeis.org

1, 2, 3, 5, 4, 8, 6, 14, 13, 11, 7, 23, 9, 17, 18, 41, 10, 38, 12, 32, 28, 20, 15, 68, 25, 26, 63, 50, 16, 53, 19, 122, 33, 29, 39, 113, 21, 35, 43, 95, 22, 83, 24, 59, 88, 44, 27, 203, 61, 74, 48, 77, 30, 188, 46, 149, 58, 47, 31, 158, 34, 56, 138, 365, 60, 98, 36, 86, 73

Offset: 1

Antti Karttunen, Jul 14 1999

nonn

Inverse of sequence A064216 considered as a permutation of the positive integers. - Howard A. Landman, Sep 25 2001
From Antti Karttunen, Dec 20 2014: (Start)
Permutation of natural numbers obtained by replacing each prime divisor of n with the next prime and mapping the generated odd numbers back to all natural numbers by adding one and then halving.
Note: there is a 7-cycle almost right in the beginning: (6 8 14 17 10 11 7). (See also comments at A249821. This 7-cycle is endlessly copied in permutations like A250249/A250250.)
The only 3-cycle in range 1 .. 402653184 is (2821 3460 5639).
For 1- and 2-cycles, see A245449.
(End)
The first 5-cycle is (1410, 2783, 2451, 2703, 2803). - Robert Israel, Jan 15 2015
From Michel Marcus, Aug 09 2020: (Start)
(5194, 5356, 6149, 8186, 10709), (46048, 51339, 87915, 102673, 137205) and (175811, 200924, 226175, 246397, 267838) are other 5-cycles.
(10242, 20479, 21413, 29245, 30275, 40354, 48241) is another 7-cycle. (End)
From Antti Karttunen, Feb 10 2021: (Start)
Somewhat artificially, also this permutation can be represented as a binary tree. Each child to the left is obtained by multiplying the parent by 3 and subtracting one, while each child to the right is obtained by applying A253888 to the parent:
                                       1
                                       |
                    ................../ \..................
                   2                                       3
         5......../ \........4                   8......../ \........6
        / \                 / \                 / \                 / \
       /   \               /   \               /   \               /   \
      /     \             /     \             /     \             /     \
    14       13         11       7          23       9          17       18
  41 10    38  12     32  28   20 15      68  25   26 63      50  16   53  19
etc.
Each node's (> 1) parent can be obtained with A253889. Sequences A292243, A292244, A292245 and A292246 are constructed from the residues (mod 3) of the vertices encountered on the path from n to the root (1).
(End)

			For n = 6, as 6 = 2 * 3 = prime(1) * prime(2), we have a(6) = ((prime(1+1) * prime(2+1))+1) / 2 = ((3 * 5)+1)/2 = 8.
For n = 12, as 12 = 2^2 * 3, we have a(12) = ((3^2 * 5) + 1)/2 = 23.

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

Inverse: A064216.
Row 1 of A251722, Row 2 of A249822.
One more than A108228, half the terms of A243501.
Fixed points: A048674.
Positions of records: A029744, their values: A246360 (= A007051 interleaved with A057198).
Positions of subrecords: A247283, their values: A247284.
Cf. A246351 (Numbers n such that a(n) < n.)
Cf. A246352 (Numbers n such that a(n) >= n.)
Cf. A246281 (Numbers n such that a(n) <= n.)
Cf. A246282 (Numbers n such that a(n) > n.), A252742 (their char. function)
Cf. A246261 (Numbers n for which a(n) is odd.)
Cf. A246263 (Numbers n for which a(n) is even.)
Cf. A246260 (a(n) reduced modulo 2), A341345 (modulo 3), A341346, A292251 (3-adic valuation), A292252.
Cf. A246342 (Iterates starting from n=12.)
Cf. A246344 (Iterates starting from n=16.)
Cf. also A003602, A003961 (A045965), A108951, A151800, A245449, A249735, A249821, A250471, A250249, A250250.
Cf. A245447 (This permutation "squared", a(a(n)).)
Other permutations whose formulas refer to this sequence: A122111, A243062, A243066, A243500, A243506, A244154, A244319, A245605, A245608, A245610, A245612, A245708, A246265, A246267, A246268, A246363, A249745, A249824, A249826, and also A183209, A254103 that are somewhat similar.
Cf. also prime-shift based binary trees A005940, A163511, A245612 and A244154.
Cf. A253888, A253889, A292243, A292244, A292245 and A292246 for other derived sequences.
Cf. A323893 (Dirichlet inverse), A323894 (sum with it), A336840 (inverse Möbius transform).

a048673 = (`div` 2) . (+ 1) . a045965
-- Reinhard Zumkeller, Jul 12 2012

f:= proc(n)
local F,q,t;
  F:= ifactors(n)[2];
  (1 + mul(nextprime(t[1])^t[2], t = F))/2
end proc:
seq(f(n),n=1..1000); # Robert Israel, Jan 15 2015

Table[(Times @@ Power[If[# == 1, 1, NextPrime@ #] & /@ First@ #, Last@ #] + 1)/2 &@ Transpose@ FactorInteger@ n, {n, 69}] (* Michael De Vlieger, Dec 18 2014, revised Mar 17 2016 *)

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ From A003961
A048673(n) = (A003961(n)+1)/2; \\ Antti Karttunen, Dec 20 2014

A048673(n) = if(1==n,n,if(n%2,A253888(A048673((n-1)/2)),(3*A048673(n/2))-1)); \\ (Not practical, but demonstrates the construction as a binary tree). - Antti Karttunen, Feb 10 2021

from sympy import factorint, nextprime, prod
def a(n):
    f = factorint(n)
    return 1 if n==1 else (1 + prod(nextprime(i)**f[i] for i in f))//2 # Indranil Ghosh, May 09 2017

(define (A048673 n) (/ (+ 1 (A003961 n)) 2)) ;; Antti Karttunen, Dec 20 2014

From Antti Karttunen, Dec 20 2014: (Start)
a(1) = 1; for n>1: If n = product_{k>=1} (p_k)^(c_k), then a(n) = (1/2) * (1 + product_{k>=1} (p_{k+1})^(c_k)).
a(n) = (A003961(n)+1) / 2.
a(n) = floor((A045965(n)+1)/2).
Other identities. For all n >= 1:
a(n) = A108228(n)+1.
a(n) = A243501(n)/2.
A108951(n) = A181812(a(n)).
a(A246263(A246268(n))) = 2*n.
As a composition of other permutations involving prime-shift operations:
a(n) = A243506(A122111(n)).
a(n) = A243066(A241909(n)).
a(n) = A241909(A243062(n)).
a(n) = A244154(A156552(n)).
a(n) = A245610(A244319(n)).
a(n) = A227413(A246363(n)).
a(n) = A245612(A243071(n)).
a(n) = A245608(A245605(n)).
a(n) = A245610(A244319(n)).
a(n) = A249745(A249824(n)).
For n >= 2, a(n) = A245708(1+A245605(n-1)).
(End)
From Antti Karttunen, Jan 17 2015: (Start)
We also have the following identities:
a(2n) = 3*a(n) - 1. [Thus a(2n+1) = 0 or 1 when reduced modulo 3. See A341346]
a(3n) = 5*a(n) - 2.
a(4n) = 9*a(n) - 4.
a(5n) = 7*a(n) - 3.
a(6n) = 15*a(n) - 7.
a(7n) = 11*a(n) - 5.
a(8n) = 27*a(n) - 13.
a(9n) = 25*a(n) - 12.
and in general:
a(x*y) = (A003961(x) * a(y)) - a(x) + 1, for all x, y >= 1.
(End)
From Antti Karttunen, Feb 10 2021: (Start)
For n > 1, a(2n) = A016789(a(n)-1), a(2n+1) = A253888(a(n)).
a(2^n) = A007051(n) for all n >= 0. [A property shared with A183209 and A254103].
(End)
a(n) = A003602(A003961(n)). - Antti Karttunen, Apr 20 2022
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/4) * Product_{p prime} ((p^2-p)/(p^2-nextprime(p))) = 1.0319981... , where nextprime is A151800. - Amiram Eldar, Jan 18 2023

New name and crossrefs to derived sequences added by Antti Karttunen, Dec 20 2014

A245606 Permutation of natural numbers: a(1) = 1, a(2n) = 1 + A003961(a(n)), a(2n+1) = A003961(1+a(n)). [Where A003961(n) shifts the prime factorization of n one step left].

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 9, 10, 7, 8, 15, 16, 11, 26, 21, 22, 13, 12, 27, 28, 25, 36, 81, 82, 19, 14, 45, 52, 125, 56, 39, 40, 29, 18, 33, 46, 17, 126, 99, 100, 31, 50, 51, 226, 41, 626, 129, 130, 89, 24, 63, 34, 35, 176, 87, 154, 59, 344, 825, 298, 115, 86, 189, 190, 43, 32, 105, 76, 23, 66, 57, 88, 53, 20

Offset: 1

Antti Karttunen, Jul 29 2014

nonn

The even bisection halved gives A245608. The odd bisection incremented by one and halved gives A245708.

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

Inverse: A245605.
Cf. A003961, A243501, A064216, A245608, A245706, A245708.
Similar entanglement permutations: A244319, A156552, A243071, A243288, A243344, A243346, A244322, A245604, A245614, A227413, A237126.

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ This function from Michel Marcus
A245606(n) = if(1==n,1,if(0==(n%2),1+A003961(A245606(n/2)),A003961(1+A245606((n-1)/2))))

;; With memoization-macro definec.
(definec (A245606 n) (cond ((= 1 n) 1) ((even? n) (A243501 (A245606 (/ n 2)))) (else (A003961 (+ 1 (A245606 (/ (- n 1) 2)))))))

a(1) = 1, a(2n) = A243501(a(n)), a(2n+1) = A003961(1+a(n)).
As a composition of related permutations:
a(n) = A064216(A245608(n)).

A244319 Self-inverse permutation of natural numbers: a(1) = 1, a(2n) = A003961(1+a(A064989(2n-1))), a(2n+1) = 1+A003961(a(A064989(2n+1)-1)).

Original entry on oeis.org

1, 3, 2, 9, 6, 5, 26, 11, 4, 21, 8, 125, 56, 25, 16, 15, 344, 115, 36, 1015, 10, 39, 204, 41, 14, 7, 52, 45, 86, 301, 176, 155, 298, 51, 50, 19, 518, 305, 22, 189, 24, 895, 1376, 49, 28, 825, 1268, 11875, 44, 35, 34, 27, 3186, 6625, 2388, 13, 454, 153, 126, 3191, 476, 131

Offset: 1

Antti Karttunen, Jul 18 2014; description corrected and PARI code added Jul 30 2014

nonn

After 1, maps each even number to a unique odd number and vice versa, i.e., for all n > 1, A000035(a(n)) XOR A000035(n) = 1, where XOR is given in A003987.

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

Cf. A000035, A003987, A003961, A064989, A243501.
Related permutations: A048673, A064216, A245609-A245610.
Similar entanglement permutations: A245605-A245606, A235491, A236854, A243347, A244152.

A003961(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ This function from Michel Marcus
A064989(n) = my(f = factor(n)); for(i=1, #f~, if((2 == f[i,1]),f[i,1] = 1,f[i,1] = precprime(f[i,1]-1))); factorback(f);
A244319(n) = if(1==n, 1, if(0==(n%2), A003961(1+A244319(A064989(n-1))), 1+A003961(A244319(A064989(n)-1))));
for(n=1, 10001, write("b244319.txt", n, " ", A244319(n)))
(Scheme, with Antti Karttunen's IntSeq-library for memoizing definec-macro)
(definec (A244319 n) (cond ((= 1 n) 1) ((even? n) (A003961 (+ 1 (A244319 (A064989 (- n 1)))))) (else (A243501 (A244319 (-1+ (A064989 n)))))))

a(1) = 1, a(2n) = A003961(1+a(A064989(2n-1))), a(2n+1) = A243501(a(A064989(2n+1)-1)).
As a composition of related permutations:
a(n) = A245609(A048673(n)) = A064216(A245610(n)).

cp's OEIS Frontend

A245607 Permutation of natural numbers, the even bisection of A245605 halved: a(n) = A245605(2*n)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Formula

A245707 Permutation of natural numbers, the odd bisection of A245605 incremented by one and halved: a(n) = (1+A245605((2*n)-1))/2.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Scheme

Scheme

Formula

A064989 Multiplicative with a(2^e) = 1 and a(p^e) = prevprime(p)^e for odd primes p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

A163511 a(0)=1. a(n) = p(A000120(n)) * Product_{m=1..A000120(n)} p(m)^A163510(n,m), where p(m) is the m-th prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A048673 Permutation of natural numbers: a(n) = (A003961(n)+1) / 2 [where A003961(n) shifts the prime factorization of n one step towards larger primes].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Scheme

Formula

Extensions

A245606 Permutation of natural numbers: a(1) = 1, a(2n) = 1 + A003961(a(n)), a(2n+1) = A003961(1+a(n)). [Where A003961(n) shifts the prime factorization of n one step left].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI