A253888 -id:A253888 - cp's OEIS frontend

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].

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

A032766 Numbers that are congruent to 0 or 1 (mod 3).

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, 22, 24, 25, 27, 28, 30, 31, 33, 34, 36, 37, 39, 40, 42, 43, 45, 46, 48, 49, 51, 52, 54, 55, 57, 58, 60, 61, 63, 64, 66, 67, 69, 70, 72, 73, 75, 76, 78, 79, 81, 82, 84, 85, 87, 88, 90, 91, 93, 94, 96, 97, 99, 100, 102, 103

Offset: 0

Patrick De Geest, May 15 1998

Omitting the initial 0, a(n) is the number of 1's in the n-th row of the triangle in A118111. - Hans Havermann, May 26 2002
Binomial transform is A053220. - Michael Somos, Jul 10 2003
Smallest number of different people in a set of n-1 photographs that satisfies the following conditions: In each photograph there are 3 women, the woman in the middle is the mother of the person on her left and is a sister of the person on her right and the women in the middle of the photographs are all different. - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Sep 22 2006
Partial sums of A000034. - Richard Choulet, Jan 28 2010
Starting with 1 = row sums of triangle A171370. - Gary W. Adamson, Feb 15 2010
a(n) is the set of values for m in which 6k + m can be a perfect square (quadratic residues of 6 including trivial case of 0). - Gary Detlefs, Mar 19 2010
For n >= 2, a(n) is the smallest number with n as an anti-divisor. - Franklin T. Adams-Watters, Oct 28 2011
Sequence is also the maximum number of floors with 3 elevators and n stops in a "Convenient Building". See A196592 and Erich Friedman link below. - Robert Price, May 30 2013
a(n) is also the total number of coins left after packing 4-curves patterns (4c2) into a fountain of coins base n. The total number of 4c2 is A002620 and voids left is A000982. See illustration in links. - Kival Ngaokrajang, Oct 26 2013
Number of partitions of 6n into two even parts. - Wesley Ivan Hurt, Nov 15 2014
Number of partitions of 3n into exactly 2 parts. - Colin Barker, Mar 23 2015
Nonnegative m such that floor(2*m/3) = 2*floor(m/3). - Bruno Berselli, Dec 09 2015
For n >= 3, also the independence number of the n-web graph. - Eric W. Weisstein, Dec 31 2015
Equivalently, nonnegative numbers m for which m*(m+2)/3 and m*(m+5)/6 are integers. - Bruno Berselli, Jul 18 2016
Also the clique covering number of the n-Andrásfai graph for n > 0. - Eric W. Weisstein, Mar 26 2018
Maximum sum of degeneracies over all decompositions of the complete graph of order n+1 into three factors. The extremal decompositions are characterized in the Bickle link below. - Allan Bickle, Dec 21 2021
Also the Hadwiger number of the n-cocktail party graph. - Eric W. Weisstein, Apr 30 2022
The number of integer rectangles with a side of length n+1 and the property: the bisectors of the angles form a square within its limits. - Alexander M. Domashenko, Oct 17 2024
The maximum possible number of 5-cycles in an outerplanar graph on n+4 vertices. - Stephen Bartell, Jul 10 2025

Indranil Ghosh, Table of n, a(n) for n = 0..10000
Allan Bickle, Nordhaus-Gaddum Theorems for k-Decompositions, Congr. Num. 211 (2012) 171-183.
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
Erich Friedman, Problem of the month November 2009
Z. Füredi, A. Kostochka, M. Stiebitz, R. Skrekovski, and D. West, Nordhaus-Gaddum-type theorems for decompositions into many parts, J. Graph Theory 50 (2005), 273-292.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 282. [Book's website]
Hsien-Kuei Hwang, S. Janson and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
International Mathematical Olympiad 2001, Hong Kong Preliminary Selection Contest, Problem #20. [Broken link; Cached copy]
Matroids Matheplanet, Number of d-generator groups of order 2^(d+1) and exponent-p class 2 (in German).
Emanuele Munarini, Topological indices for the antiregular graphs, Le Mathematiche, Vol. 76, No. 1 (2021), pp. 277-310, see p. 302.
Kival Ngaokrajang, Illustration of initial terms (U).
Eric Weisstein's World of Mathematics, Andrásfai Graph
Eric Weisstein's World of Mathematics, Clique Covering Number
Eric Weisstein's World of Mathematics, Cocktail Party Graph
Eric Weisstein's World of Mathematics, Hadwiger Number
Eric Weisstein's World of Mathematics, Independence Number
Eric Weisstein's World of Mathematics, Web Graph
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A006578 (partial sums), A000034 (first differences), A016789 (complement).
Essentially the same: A049624.
Column 1 (the second leftmost) of triangular table A026374.
Column 1 (the leftmost) of square array A191450.
Row 1 of A254051.
Row sums of A171370.
Cf. A066272 for anti-divisors.
Cf. A253888 and A254049 (permutations of this sequence without the initial zero).
Cf. A254103 and A254104 (pair of permutations based on this sequence and its complement).
Cf. A000035, A000217, A000982, A001651, A002620, A002717, A003945.
Cf. A004396, A004526, A007310, A007494, A008619, A030308, A035360.
Cf. A047270, A049615, A052928, A053220, A070893, A084056, A092942.
Cf. A118111, A132463, A133083, A196592, A249745.

a032766 n = div n 2 + n  -- Reinhard Zumkeller, Dec 13 2014
(MIT/GNU Scheme) (define (A032766 n) (+ n (floor->exact (/ n 2)))) ;; Antti Karttunen, Jan 24 2015

&cat[ [n, n+1]: n in [0..100 by 3] ]; // Vincenzo Librandi, Nov 16 2014

a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=a[n-2]+3 od: seq(a[n], n=0..69); # Zerinvary Lajos, Mar 16 2008
seq(floor(n/2)+n, n=0..69); # Gary Detlefs, Mar 19 2010
select(n->member(n mod 3,{0,1}), [$0..103]); # Peter Luschny, Apr 06 2014

a[n_] := a[n] = 2a[n - 1] - 2a[n - 3] + a[n - 4]; a[0] = 0; a[1] = 1; a[2] = 3; a[3] = 4; Array[a, 60, 0] (* Robert G. Wilson v, Mar 28 2011 *)
Select[Range[0, 200], MemberQ[{0, 1}, Mod[#, 3]] &] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2012 *)
Flatten[{#,#+1}&/@(3Range[0,40])] (* or *) LinearRecurrence[{1,1,-1}, {0,1,3}, 100] (* or *) With[{nn=110}, Complement[Range[0,nn], Range[2,nn,3]]] (* Harvey P. Dale, Mar 10 2013 *)
CoefficientList[Series[x (1 + 2 x) / ((1 - x) (1 - x^2)), {x, 0, 100}], x] (* Vincenzo Librandi, Nov 16 2014 *)
Floor[3 Range[0, 69]/2] (* L. Edson Jeffery, Jan 14 2017 *)
Drop[Range[0,110],{3,-1,3}] (* Harvey P. Dale, Sep 02 2023 *)

PARI
```
{a(n) = n + n\2}
```

concat(0, Vec(x*(1+2*x)/((1-x)*(1-x^2)) + O(x^100))) \\ Altug Alkan, Dec 09 2015

[int(3*n//2) for n in range(101)] # G. C. Greubel, Jun 23 2024

G.f.: x*(1+2*x)/((1-x)*(1-x^2)).
a(-n) = -A007494(n).
a(n) = A049615(n, 2), for n > 2.
From Paul Barry, Sep 04 2003: (Start)
a(n) = (6n - 1 + (-1)^n)/4.
a(n) = floor((3n + 2)/2) - 1 = A001651(n) - 1.
a(n) = sqrt(2) * sqrt( (6n-1) (-1)^n + 18n^2 - 6n + 1 )/4.
a(n) = Sum_{k=0..n} 3/2 - 2*0^k + (-1)^k/2. (End)
a(n) = 3*floor(n/2) + (n mod 2) = A007494(n) - A000035(n). - Reinhard Zumkeller, Apr 04 2005
a(n) = 2 * A004526(n) + A004526(n+1). - Philippe Deléham, Aug 07 2006
a(n) = 1 + ceiling(3*(n-1)/2). - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Sep 22 2006
Row sums of triangle A133083. - Gary W. Adamson, Sep 08 2007
a(n) = (cos(Pi*n) - 1)/4 + 3*n/2. - Bart Snapp (snapp(AT)coastal.edu), Sep 18 2008
A004396(a(n)) = n. - Reinhard Zumkeller, Oct 30 2009
a(n) = floor(n/2) + n. - Gary Detlefs, Mar 19 2010
a(n) = 3n - a(n-1) - 2, for n>0, a(0)=0. - Vincenzo Librandi, Nov 19 2010
a(n) = n + (n-1) - (n-2) + (n-3) - ... 1 = A052928(n) + A008619(n-1). - Jaroslav Krizek, Mar 22 2011
a(n) = a(n-1) + a(n-2) - a(n-3). - Robert G. Wilson v, Mar 28 2011
a(n) = Sum_{k>=0} A030308(n,k) * A003945(k). - Philippe Deléham, Oct 17 2011
a(n) = 2n - ceiling(n/2). - Wesley Ivan Hurt, Oct 25 2013
a(n) = A000217(n) - 2 * A002620(n-1). - Kival Ngaokrajang, Oct 26 2013
a(n) = Sum_{i=1..n} gcd(i, 2). - Wesley Ivan Hurt, Jan 23 2014
a(n) = 2n + floor((-n - (n mod 2))/2). - Wesley Ivan Hurt, Mar 31 2014
A092942(a(n)) = n for n > 0. - Reinhard Zumkeller, Dec 13 2014
a(n) = floor(3*n/2). - L. Edson Jeffery, Jan 18 2015
a(n) = A254049(A249745(n)) = (1+A007310(n)) / 2 for n >= 1. - Antti Karttunen, Jan 24 2015
E.g.f.: (3*x*exp(x) - sinh(x))/2. - Ilya Gutkovskiy, Jul 18 2016
Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/(6*sqrt(3)) + log(3)/2. - Amiram Eldar, Dec 04 2021

Better description from N. J. A. Sloane, Aug 01 1998

cp's OEIS Frontend

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

A032766 Numbers that are congruent to 0 or 1 (mod 3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

A254049 Odd bisection of A048673: a(n) = A048673(2*n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A253889 a(n) = A048673(floor(A064216(n)/2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula