13
\$\begingroup\$

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

Task

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
\$\endgroup\$
  • \$\begingroup\$ Can we return True instead of 1? \$\endgroup\$ – Dennis Jun 6 '16 at 7:05
  • \$\begingroup\$ @Dennis After some consideration, I’ve decided my answer is no. The output must at least look like a number. \$\endgroup\$ – Lynn Jun 9 '16 at 16:38

12 Answers 12

6
\$\begingroup\$

Jelly, 10 bytes

ÆE;0s2UFÆẸ

Try it online! or verify all test cases.

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.
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

Jelly, 17 16 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.
    ©               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.
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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".

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ input() works in Python 2? \$\endgroup\$ – NoOneIsHere Jun 6 '16 at 4:51
  • \$\begingroup\$ @NoOneIsHere Yes, it is the equivalent of eval(input()) in Python 3. \$\endgroup\$ – Mego Jun 6 '16 at 7:28
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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].

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Python 2, 112 109 108 95 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.

    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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Pyth, 25 bytes

JfP_TSfP_ThQ*F+1m@Jx1xJdP

Test suite.

Explanation

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Julia, 155 131 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)

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Actually, 15 bytes

w`i;r♂Pí1^Pn`Mπ

Try it online!

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 22 bytes

Ó¾‚˜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

Try it online

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.