# Swap prime exponents with their neighbours

(Follow-up to my question about swapping bits with their neighbours.)

Given a positive integer x = (2a · 3b) · (5c · 7d) · (11e · 13f) · …, print the integer obtained by swapping the exponents in this factorization for each successive pair of primes, y = (2b · 3a) · (5d · 7c) · (11f · 13e) · …

A061898 in the OEIS. This is , so the shortest program (in bytes) wins!

# Test cases

1 -> 1
2 -> 3
3 -> 2
10 -> 21
37 -> 31
360 -> 756
12345 -> 11578
67895678 -> 125630871

• Can we return True instead of 1? Commented Jun 6, 2016 at 7:05
• @Dennis After some consideration, I’ve decided my answer is no. The output must at least look like a number.
– lynn
Commented Jun 9, 2016 at 16:38

# Jelly, 10 bytes

ÆE;0s2UFÆẸ


### How it works

ÆE;0s2UFÆẸ  Main link. Argument: n

ÆE          Yield the exponents of n's prime factorization.
;0        Append a zero.
s2      Split into pairs.
U     Upend; reverse each pair.
F    Flatten the resulting list of pairs.
ÆẸ  Convert the prime exponents to integer.


# Jelly, 1716 11 bytes

5 bytes thanks to Dennis.

ÆfÆC’^1‘ÆNP


Try it online!

### Explanation

ÆfÆC’^1‘ÆNP   Main monadic chain. Argument: n

Æf            Yield the prime factors of n.
ÆC          For each factor, count the number of primes below it.
This effectively yields their indices.
’         Decrement [each] by 1.
^1       Xor with 1
‘      Increment [each] by 1.
ÆN    Find their corresponding primes.
P   Yield their product.


## Previous 16-byte version

ÆnÆRiÐ€Æf’^1‘ÆNP


Try it online!

### Explanation

ÆnÆRiÐ€Æf’^1‘ÆNP   Main monadic chain. Argument: n

Æn                 Yield the next prime from n.
ÆR               Yield all primes from 2 to it.
Æf          Yield prime factors of n
iÐ€            Yield their index in the prime list.
’         Decrement [each] by 1.
^1       Xor with 1
‘      Increment [each] by 1.
ÆN    Find their corresponding primes.
P   Yield their product.


## Previous 17-byte version:

ÆnÆR©iÐ€Æf’^1‘ị®P


Try it online!

### Explanation

ÆnÆR©iÐ€Æf’^1‘ị®P   Main monadic chain. Argument: n

Æn                  Yield the next prime from n.
ÆR                Yield all primes from 2 to it.
Æf          Yield prime factors of n
iÐ€            Yield their index in the prime list.
’         Decrement [each] by 1.
^1       Xor with 1
‘      Increment [each] by 1.
ị®    Find their corresponding primes in
the list in register.
P   Yield their product.


## Mathematica, 70 69 bytes

1##&@@(Prime[BitXor[PrimePi@#+1,1]-1]^#2&)@@@FactorInteger@#/._@_->1&


An unnamed function which takes and returns an integer. It throws an error on input 1 but still computes the correct result.

### Explanation

As usual, due to all the syntactic sugar, the reading order is a bit funny. A & on the right defines an unnamed function and its arguments are referred to by #, #2, #3, etc.

...FactorInteger@#...


We start by factoring the input. This gives a list of pairs {prime, exponent} e.g. input 12 gives {{2, 2}, {3, 1}}. Somewhat inconveniently, 1 gives {{1, 1}}.

(...&)@@@...


This applies the function on the left to the list of integers at level 1, that is the function is called for each pair, passing the prime and exponent in as separate arguments, and then returns a list of the results. (This is similar to mapping the function over the list, but receiving two separate arguments is more convenient than receiving a pair.)

...PrimePi@#...


We compute the number of primes up to and including the (prime) input using the built-in PrimePi. This gives us the index of the prime.

...BitXor[...+1,1]-1...


The result is incremented, XOR'ed with 1 and decremented again. This swaps 1 <-> 2, 3 <-> 4, 5 <-> 6, ..., i.e. all 1-based indices. Note that input 1 will yield 0 for PrimePi which is then mapped to -1 in this process. We'll deal with that later.

 ...Prime[...]^#2...


We now obtain the nth prime (where n is the result from the previous computation), which is the correctly swapped prime, and raise it to the power of the original prime in the factorisation of the input. At this point Prime[-1] will throw an error but will return itself unevaluated. The power in this case is 1 so that the entire process so far yields {Prime[-1]} for input 1 and a list of correct prime powers for all other inputs.

 1##&@@...


Next, we just multiply up all prime powers. 1##& is a standard golfing trick for the Times function. See this tip (section "Sequences of arguments") for how it works.

Finally, we need to take care of input 1 for which all of the above resulted in Prime[-1]. We can easily fix that with a simple replacement rule. Remember that f@x is short for f[x]. We just want to match any expression of that form (since all other results will be integers, i.e. atomic expressions), and replace it with a 1:

.../._@_->1


Here, /. is short for ReplaceAll, _@_ is a pattern for anything of the form f[x] (i.e. any compound expression with a single child) and ->1 says "replace with 1".

# Python 2, 149 139 bytes

10 bytes thanks to Dennis.

n=input()
p=f=1;w=[2]
while w[-1]<=n:f*=p;p+=1;w+=[p]*(-~f%p<1)
r=p=1;w=w[1:]
while n>1:
p+=1
while n%p<1:n/=p;r*=w[w.index(p)^1]
print r

• input() works in Python 2? Commented Jun 6, 2016 at 4:51
• @NoOneIsHere Yes, it is the equivalent of eval(input()) in Python 3.
– user45941
Commented Jun 6, 2016 at 7:28

# Python 2, 11210910895 94 bytes

f=lambda n,k=4,m=6,p=[3,2]:1/n or n%p[1]and f(n,k+1,m*k,m*m%k*[k]+p)or p[len(p)*2%4]*f(n/p[1])


Test it on Ideone.

### How it works

When f is called, it first computes 1/n. If the result is non-zero, n is 1 and f returns 1.

If n > 1, the following happens.

• If n is not divisible by p[1] (initially 2), n%p[1] yields a truthy value and

  f(n,k+1,m*k,m*m%k*[k]+p)


gets called.

This branch generates prime number until the penultimate one evenly divides n. To do so, it uses the following corollary of Wilson's theorem.

At all times, m is equal to the factorial of k - 1 (initially 6 = 3! and 4. In each iteration, the result of m*m%k*[k] gets prepended to the list of primes p. By the corollary, m*m%k is 1 if k is prime and 0 if not, so this prepends k to p if and only if k is a prime number.

• If n is divisible by p[1], n%p[1] yields 0 and

  p[len(p)*2%4]*f(n/p[1])


gets executed.

If p contains an even amount of prime numbers, len(p)*2%4 will yield 0 and the first multiplicand takes the value of p[0]. If p contains an odd amount of prime numbers, len(p)*2%4 will yield 2 and the first multiplicand takes the value of p[2].

In either case, this is the prime whose exponents has to get swapped with the one of p[1], so we divide n by p[1] (decreasing the exponent by 1) and multiply the result of f(n/p[1]) by the corresponding prime (increasing the exponent by 1).

Note that f(n/p[1]) resets k, m and p to their default values. f(n/p[1],k,m,p) would improve efficiency, at the cost of six extra bytes.

# MATL, 17 bytes

EZqGYfy&mt2\Eq+)p


Try it online!

### Explanation

This doesn't use the exponents directly. Instead, it swaps each (possibly repeated) prime factor by the next or the preceding prime.

EZq    % Implicit input. Multiply by 2
Zq     % Array with sequence of primes up to that (this is more than enough)
GYf    % Prime factors of input, with possible repetitions
y      % Duplicate array with sequence of primes
&m     % Indices of prime factors in the sequence of primes
t2\    % Duplicate, modulo 2. Gives 0 for even indices, 1 for odd
Eq     % Multiply by 2, add 1. Transforms 0 / 1 into -1 / 1
+      % Add. This modifies the indices to perform the swapping
)      % Apply the new indices into the sequence of primes
p      % Product. Implicit display


# Julia, 64 bytes

~=primes
!n=prod(t->(~3n)[endof(~t[1])+1$1-1]^t[2],factor(2n))/3  Try it online! The last test case requires too much memory for TIO, but I've verified it locally. ### How it works To avoid special-casing input 1 – the product of an empty dictionary is not defined – we multiply the input n by 2 and divide the final result by its pair 3. factor(2n) gives all positive exponents of prime factors of 2n as a dictionary. When iterating over the dictionary, we'll get key-value/prime-exponent pairs. The function prod will take these pairs, apply the anonymous function t->... to them and return the product of the results. For each pair t = (p,e), endof(~t[1]) or endof(primes(t[1])) return k, the number of primes that are less or equal to p, meaning that p is the kth prime. +1$1-1 will increment k, XOR k + 1 with 1 and decrement the result. If k is odd, k + 1 is even, so the XOR increments and the final result is k + 1. If k is even, k + 1 is odd, so the XOR decrements and the final result is k - 1.

Finally, we compute all prime numbers less or equal to 3n with (~3n) or primes(3n) (the highest prime factor of 2n is less or equal to n if n > 2, and there's always a prime between n and 2n), select the one at index k + 1 or k - 1, and elevate it to the eth power with ^t[2].

# Pyth, 25 bytes

JfP_TSfP_ThQ*F+1m@Jx1xJdP


Test suite.

## Explanation

JfP_TSfP_ThQ*F+1m@Jx1xJdP

Q    get input
fP_T      find the first prime after it
S          range from 1 to that prime
fP_T           filter for the primes
J               assign to J

P  prime factorize input
m      d   for each factor
xJ    find its index in J
x1      xor with 1
@J        find the corresponding entry in J
*F+1           product of the whole list


# Julia, 155131 127 bytes

n->(x=[sort([merge([p=>0for p=primes(n+1)],factor(n))...]);1=>0];prod([x[i-1][1]^x[i][2]*x[i][1]^x[i-1][2]for i=2:2:endof(x)]))


This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable. It requires a Julia version < 0.5 because the prime functionality has been removed from Base in 0.5.

Ungolfed:

function f(n::Int)
# Create an array of pairs by merging the Dict created from factoring n
# with all primes less than n+1 with a 0 exponent. Append an extra pair
# to account for 1 and situations where x would otherwise have odd length.
x = [sort([(merge([p=>0 for p in primes(n+1)], factor(n))...]); 1=>0]

# Compute a^d * c^b, where a and c are primes with b and d as their
# respective exponents.
prod([x[i-1][1]^x[i][2] * x[i][1]^x[i-1][2] for i = 2:2:endof(x)])
end


Try it online! (Includes all test cases)

## Actually, 15 bytes

wi;r♂Pí1^PnMπ


Try it online!

Explanation:

wi;r♂Pí1^PnMπ
w                prime factorization
          M   map (for (p,e) in factorization):
i;               flatten, make a copy of p
r♂P            [prime[i] for i in range(p)]
í           index (essentially the 0-based prime index of p)
1^         XOR with 1
P        prime[n]
n       repeat e times
π  product


## 05AB1E, 22 bytes

Ó¾‚˜2ô€R˜DgL<Ø)øvysmP


Explained

Ó¾‚˜                    # list of primeexponents with a 0 appended: n=10 -> [1,0,1,0]
2ô                  # split into pairs: [[1,0],[1,0]]
€R˜               # reverse each pair and flatten: [0,1,0,1]
DgL<Ø          # get list of primes corresponding to the exponents: [2,3,5,7]
)ø        # zip lists: [[0,2],[1,3],[0,5],[1,7]]
vysm   # raise each prime to its new exponent: [1,3,1,7]
P  # product: 21


Try it online

# J, 21 bytes

([:,_2|.\,&0)&.(_&q:)


Gets the prime exponents of n as prime powers with zeros. Then partition them into nonoverlapping sublists of size 2 while filling with an extra zero. Then reverse each sublist, and flatten them into a list. Finally, convert back from prime exponents to a number.

## Usage

   f =: ([:,_2|.\,&0)&.(_&q:)
(,.f"0) 1 2 3 10 37 360 12345
1     1
2     3
3     2
10    21
37    31
360   756
12345 11578
f 67895678x
125630871


## Explanation

([:,_2|.\,&0)&.(_&q:)  Input: n
_&q:   Obtain the list of prime exponents
(           )&.        Apply to the list of prime exponenets
,&0           Append a zero to the end of the list
_2  \              Split the list into nonoverlapping sublists of size 2
|.               Reverse each sublist
[:,                   Flatten the list of sublists into a list
&.(    )  Apply the inverse of (Obtain the list of prime exponents)
to convert back to a number and return it


# Stax, 16 bytes

â↕ÿ╓d8‼Qlì"┌nq╟ì


Run and debug it

# 05AB1E, 13 bytes

Ó0ª2ôí˜ā<ØsmP


Or alternatively:

xÅPsÓ0ª2ôí˜mP


Explanation:

Ó              # Get all prime exponents of the (implicit) input-integer
0ª            # Append a 0
2ô          # Split it int parts of size 2
í         # Reverse each inner pair
˜        # Flatten the list
ā       # Push a list in the range [1,length] (without popping the list)
<      # Decrease each by 1 to the range [0,length)
Ø     # Get the n'th prime of each value
s    # Swap so the earlier list is at the top
m   # Take the primes to the power of the exponents
P  # And then take the product
# (after which the result is output implicitly)

x              # Double the (implicit) input-integer (without popping)
ÅP            # Pop and push a list of all prime numbers <= this doubled input
s           # Swap so the input is at the top of the stack
Ó0ª2ôí˜    # Same as above
m   # Take each prime to the power of the exponents