Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
(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 code-golf, so the shortest program (in bytes) wins!
1 -> 1
2 -> 3
3 -> 2
10 -> 21
37 -> 31
360 -> 756
12345 -> 11578
67895678 -> 125630871
ÆE;0s2UFÆẸ
Try it online! or verify all test cases.
Æ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.
5 bytes thanks to Dennis.
ÆfÆC’^1‘ÆNP
Æ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.
ÆnÆRiЀÆf’^1‘ÆNP
Æ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.
ÆnÆR©iЀÆf’^1‘ị®P
Æ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.
© Store to register.
Æ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.
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.
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".
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
eval(input()) in Python 3.
\$\endgroup\$
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.
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.
EZqGYfy&mt2\Eq+)p
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
~=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.
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].
JfP_TSfP_ThQ*F+1m@Jx1xJdP
JfP_TSfP_ThQ*F+1m@Jx1xJdP
Q get input
h add one
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
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)
w`i;r♂Pí1^Pn`Mπ
Explanation:
w`i;r♂Pí1^Pn`Mπ
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
Ó¾‚˜2ô€R˜DgL<Ø)øvy`smP
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]]
vy`sm # raise each prime to its new exponent: [1,3,1,7]
P # product: 21
([:,_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.
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
([:,_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
Ó0ª2ôí˜ā<ØsmP
Try it online or verify all test cases.
Or alternatively:
xÅPsÓ0ª2ôí˜mP
Try it online or verify all test cases.
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
# (any additional trailing primes will be discarded)
P # And then take the product
# (after which the result is output implicitly)
