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

Author

Amarnath Murthy, Aug 11 2002

Keywords

• nonn

Comments

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

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

Row 2 and column 2 of A059897.

Programs

Maple

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

Mathematica

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 *)

PARI

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

Python

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

Formula

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

Extensions

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