A118967 -id:A118967 - cp's OEIS frontend

A073675 Rearrangement of natural numbers such that a(n) is the smallest proper divisor of n not included earlier but if no such divisor exists then a(n) is the smallest proper multiple of n not included earlier, subject always to the condition that a(n) is not equal to n.

2, 1, 6, 8, 10, 3, 14, 4, 18, 5, 22, 24, 26, 7, 30, 32, 34, 9, 38, 40, 42, 11, 46, 12, 50, 13, 54, 56, 58, 15, 62, 16, 66, 17, 70, 72, 74, 19, 78, 20, 82, 21, 86, 88, 90, 23, 94, 96, 98, 25, 102, 104, 106, 27, 110, 28, 114, 29, 118, 120, 122, 31, 126, 128, 130, 33, 134, 136

Offset: 1

Amarnath Murthy, Aug 11 2002

nonn

The parity of the sequence is E,D,E,E,E,D,E,E,E,D,E,E,E,D,E,E,E,D,E,E,E,D,..., that is, an D followed by three E's from the second term onwards.
Closely related to A035263: if A035263(n) = 1, a(n) = 2n; otherwise a(n)=n/2. - Franklin T. Adams-Watters, Feb 02 2006
This permutation is self-inverse. This is the case r=2 of sequences where a(n)=floor(n/r) if floor(n/r)>0 and not already in the sequence, a(n) = floor(n*r) otherwise. All such sequences (for r>=1) are permutations of the natural numbers. - Franklin T. Adams-Watters, Feb 06 2006
Take the list of positive integers L. At each step n swap L(n) with L(2*L(n)). - Ali Sada, Jun 18 2025

Matches A118967 for all non-powers-of-two. - Carl R. White, Aug 23 2010

Row 2 and column 2 of A059897.

a:= proc(n) local i, m; m:=n;
      for i from 0 while irem(m, 2, 'r')=0 do m:=r od;
      m*2^`if`(irem(i, 2)=1, i-1, i+1)
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, Feb 10 2014

a[n_] := Module[{i, m = n}, For[i = 0, {q, r} = QuotientRemainder[m, 2]; r == 0, i++, m = q]; m*2^If[Mod[i, 2] == 1, i-1, i+1]]; Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Jun 10 2015, after Alois P. Heinz *)

a(n) = if (valuation(n, 2) % 2, n/2, 2*n); \\ Michel Marcus, Mar 17 2018

def A073675(n): return n>>1 if (~n & n-1).bit_length()&1 else n<<1 # Chai Wah Wu, Aug 08 2025

If valuation(n,2) is even, a(n) = 2n; otherwise a(n)=n/2, where valuation(n,2) = A007814(n) is the exponent of the highest power of 2 dividing n. - Franklin T. Adams-Watters, Feb 06 2006, Jul 31 2009

a(k*2^m) = k*2^(m+(-1)^m), m >= 0, odd k >= 1. - Carl R. White, Aug 23 2010

More terms and comment from Franklin T. Adams-Watters, Feb 06 2006, Jul 31 2009
More terms from Franklin T. Adams-Watters, Feb 06 2006
Edited by N. J. A. Sloane, Jul 31 2009
Typo fixed by Charles R Greathouse IV, Apr 29 2010

A366389 Variant of bijective bit-reverse of n (A057889) for which it holds that a(n) == n (mod 3).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 26, 12, 22, 14, 15, 16, 17, 18, 25, 20, 21, 13, 29, 24, 19, 11, 27, 28, 23, 30, 31, 32, 33, 34, 98, 36, 82, 50, 57, 40, 74, 42, 106, 104, 45, 58, 122, 48, 70, 38, 51, 88, 86, 54, 118, 56, 39, 46, 110, 60, 94, 62, 63, 64, 65, 66, 97, 68, 81, 49, 113, 72, 73, 41, 105, 100, 89, 114, 121

Offset: 0

Antti Karttunen, Oct 22 2023

Like A057889, also this is a self-inverse permutation of nonnegative integers.

Cf. A010872, A030101, A057889, A073675, A366378, A366379, A366390 (Dirichlet inverse), A366392.

Cf. also A118967.

A030101(n) = if(n<1,0,subst(Polrev(binary(n)),x,2));
A057889(n) = if(!n,n,A030101(n/(2^valuation(n,2))) * (2^valuation(n, 2)));
A073675(n) = if(valuation(n,2)%2,n/2,2*n);
A366389(n) = { my(u=A057889(n)); if(!((u-n)%3),u,A073675(u)); };

If A057889(n) == n mod 3, then a(n) = A057889(n), otherwise a(n) = A073675(A057889(n)) = A057889(A073675(n)).

For all n >= 0, A010872(a(n)) = A010872(n).

A118966 a(n) = (n+1)/2 if n occurs among the first n-1 terms of the sequence, otherwise a(n) = 2*n - 1.

Original entry on oeis.org

1, 3, 2, 7, 9, 11, 4, 15, 5, 19, 6, 23, 25, 27, 8, 31, 33, 35, 10, 39, 41, 43, 12, 47, 13, 51, 14, 55, 57, 59, 16, 63, 17, 67, 18, 71, 73, 75, 20, 79, 21, 83, 22, 87, 89, 91, 24, 95, 97, 99, 26, 103, 105, 107, 28, 111, 29, 115, 30, 119, 121, 123, 32, 127, 129, 131, 34, 135

Offset: 1

Leroy Quet, May 07 2006

Sequence is a permutation of the positive integers. It is also its own inverse (i.e., a(a(n)) = n).
From Thomas Scheuerle, Dec 24 2020: (Start)
The same sequence can be generated by defining a(0)=0 and a(1)=1 and, for each n>1, choosing the smallest unused positive integer such that max(a(n)/n) will increase or min(a(n)/n) will decrease.
Proof: Three conditions are required to guarantee that the definitions are equivalent. The first condition is that this is a permutation; this is satisfied because this is a permutation involution. This is because (n+1)/2 is the inverse function of 2n-1, which is applied only if n is not already used in the sequence. The second condition is that, with each new term, max(a(n)/n) increases or min(a(n)/n) decreases. This is obviously the case because the next term would be either 2n-1, with would increase max(a(n)/n), or (n+1)/2, which would decrease min(a(n)/n). The third and last condition is that each new term is the smallest possible number satisfying the first two conditions. This holds because 2n-1 is the smallest possible number m*n+b where the slope m is > 1 and a(1) = 1. (A slope > 1 is needed for condition 2.)
(End)

Index entries for sequences that are permutations of the natural numbers

Cf. A118967, A073675.

% Program to test alternative definition:
%"Permutation of natural number such that max(a(n)/n)-min(a(n)/n) increases monotonously by using smallest possible next number, a(0) = 0, a(1) = 1."
function a = A118966( max_n )
    a(1) = 0;
    a(2) = 1;
    m_max = 1;
    m_min = 1;
    n = 3;
    t = 1;
    while n <= max_n
        % search next number t not yet used in a
        while ~isempty(find(a==t, 1))
            t = t+1;
        end
        m = t/(n-1);
        % check slope m
        if m < m_min || m > m_max
            % we found a candidate
            a(n) = t;
            n = n+1;
            if m > m_max
                m_max = m;
            end
            if m < m_min
                m_min = m;
            end
            t = 1;
        else
            % number t does not yet fit
            t = t+1;
        end
    end
end
% Thomas Scheuerle, Dec 24 2020

f[s_] := Block[{n = Length@s}, Append[s, If[MemberQ[s, n], (n + 1)/2, 2n - 1]]]; Rest@Nest[f, {1}, 70] (* Robert G. Wilson v, May 16 2006 *)
(* Program to test alternative definition : *)
(* "Permutation of natural number such that max(a(n)/n)-min(a(n)/n) increases monotonously by using smallest possible next number, a(0) = 0, a(1) = 1." *)
Block[{a = {0, 1}, b = {1}, c = {0}, k, r, s}, Do[k = 2; While[Nand[Set[s, Max[#] - Min[#]] > c[[-1]], FreeQ[a, k]] &@ Append[b, Set[r, k/i]], k++]; AppendTo[a, k]; AppendTo[b, r]; AppendTo[c, s], {i, 2, 55}]; a] (* Michael De Vlieger, Dec 11 2020 *)

a(n) = A073675(n-1) + 1. - Thomas Scheuerle, Dec 27 2020

More terms from Robert G. Wilson v, May 16 2006

cp's OEIS Frontend

A073675 Rearrangement of natural numbers such that a(n) is the smallest proper divisor of n not included earlier but if no such divisor exists then a(n) is the smallest proper multiple of n not included earlier, subject always to the condition that a(n) is not equal to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A366389 Variant of bijective bit-reverse of n (A057889) for which it holds that a(n) == n (mod 3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A118966 a(n) = (n+1)/2 if n occurs among the first n-1 terms of the sequence, otherwise a(n) = 2*n - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

MATLAB

Mathematica

Formula

Extensions