[seqfan] More on Permutations of Natural Numbers

[Brad Klee]

Hi Seqfans,

Here's another greedy scheme for permuting the natural numbers:

Each term a( n ) satisfies four properties:

1. divisible by all prime factors of n.
2. divisible by only the prime factors of n.
3. not equal to any of the terms a( 1 ), a( 2 ), ... a( n - 1 )
4. Smallest number satisfying 1-3 if A005361(n) is even.
    Second smallest number satisfying 1-3 if A005361(n) is odd.

The first few terms are:

1, 4, 9, 2, 25, 12, 49, 16, 3, 20, 121, 6, 169, 28, 45, 8, 289, 18,
361 ...

And a few easily proven facts:

This sequence is permutation of the integers.
All primes a(n) = p occur at n = p^2.
multiples of a number x have density 1 / x.
squarefee equivalent to natural numbers.

thanks,

Brad

Mathematica code ( though slow ):


Clear at a
a[1, _, _] = 1
a[n_, op_, log_] :=
 a[n, op, log] = With[{pf = FactorInteger[n][[All, 1]]},
   Complement[
     Times @@ (pf^#) & /@ Tuples[Range[10], Length at pf],
     a[#, op, log] & /@ Range[1, n - 1]
     ][[ If[log[op @@ FactorInteger[n][[All, 2]] ], 1, 2] ]]
   ]

1

l1o = a[#, Plus, OddQ] & /@ Range[1000];
l1e = a[#, Plus, EvenQ] & /@ Range[1000];
l2o = a[#, Times, OddQ] & /@ Range[1000];
l2e = a[#, Times, EvenQ] & /@ Range[1000];