Поменяйте местами простые числа со своими соседями

13

(В продолжение моего вопроса об обмене битами со своими соседями .)

задача

Если дано положительное целое число x = (2 a  · 3 b ) · (5 c  · 7 d ) · (11 e  · 13 f ) ·… , выведите целое число, полученное путем замены показателей степени в этой факторизации для каждой последующей пары простых чисел, у = (2 б  · 3 а ) · (5 д  · 7 с ) · (11 ф  · 13 э ) ·…

A061898 в ОЕИС . Это код-гольф , поэтому выигрывает самая короткая (в байтах) программа!

Контрольные примеры

1 -> 1
2 -> 3
3 -> 2
10 -> 21
37 -> 31
360 -> 756
12345 -> 11578
67895678 -> 125630871
code-golf primes Линн
источник
Можем ли мы вернуть True вместо 1 ?
Деннис
@ Денис После некоторого рассмотрения я решил, что мой ответ - нет. Вывод должен хотя бы выглядеть как число.
Линн

Ответы:

4

Желе, 17 16 11 байт

5 байтов благодаря Денису.

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

Предыдущая 16-байтовая версия

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

Предыдущая 17-байтовая версия:

Æ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.
Дрянная Монахиня
источник
3

Mathematica, 70 69 байт

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

Безымянная функция, которая принимает и возвращает целое число. Выдает ошибку при вводе, 1но все равно вычисляет правильный результат.

объяснение

Как обычно, из-за всего синтаксического сахара, порядок чтения немного забавен. &На право определяет неназванные функции и ее аргументы ссылаются #, #2, #3и т.д.

...FactorInteger@#...

Мы начнем с факторинга ввода. Это дает список пар, {prime, exponent}например, ввод 12дает {{2, 2}, {3, 1}}. Несколько неудобно, 1дает {{1, 1}}.

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

Это применяет функцию слева к списку целых чисел на уровне 1, то есть функция вызывается для каждой пары, передавая простое и экспоненту в качестве отдельных аргументов, а затем возвращает список результатов. (Это похоже на отображение функции по списку, но получение двух отдельных аргументов удобнее, чем получение пары.)

...PrimePi@#...

Мы вычисляем количество простых чисел вплоть до (простого) ввода с использованием встроенного PrimePi. Это дает нам индекс простого числа.

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

Результат увеличивается, XOR 1и снова уменьшается. Это перестановки 1 <-> 2, 3 <-> 4, 5 <-> 6, ..., т.е. все индексы, основанные на 1. Обратите внимание, что входные данные 1дадут, 0для PrimePiкоторых затем отображается -1в этом процессе. Мы разберемся с этим позже.

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

Теперь мы получим n- е простое число (где n - результат предыдущего вычисления), которое является правильно переставленным простым, и возведем его в степень исходного простого числа при факторизации входных данных. В этот момент Prime[-1]выдаст ошибку, но вернет себя без оценки. Мощность в этом случае такова, 1что весь процесс до сих пор дает данные {Prime[-1]}для ввода 1и список правильных простых степеней для всех других входов.

 1##&@@...

Далее мы просто умножаем все основные силы. 1##&стандартная игра в гольф для этой Timesфункции. Смотрите этот совет (раздел «Последовательности аргументов»), чтобы узнать, как это работает.

Наконец, нам нужно позаботиться о том, 1что привело ко всему вышеперечисленному Prime[-1]. Мы можем легко исправить это с помощью простого правила замены. Помните, что f@xэто сокращение от f[x]. Мы просто хотим сопоставить любое выражение этой формы (поскольку все остальные результаты будут целыми числами, то есть атомарными выражениями) и заменить его на 1:

.../._@_->1

Здесь, /.сокращенно ReplaceAll, _@_это шаблон для чего-либо в форме f[x](то есть для любого составного выражения с одним дочерним элементом ), и он ->1говорит «заменить на 1».

Мартин Эндер
источник
3

Python 2, 149 139 байт

10 байтов благодаря Денису.

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()работает в Python 2?
NoOneIsHere
@NoOneIsHere Да, это эквивалент eval(input())в Python 3.
Мего
2

MATL , 17 байт

EZqGYfy&mt2\Eq+)p

Попробуйте онлайн!

объяснение

Это не использует экспоненты напрямую. Вместо этого он меняет каждый (возможно повторяющийся) простой фактор на следующий или предыдущий простой.

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
Луис Мендо
источник
2

Юлия, 64 байта

~=primes
!n=prod(t->(~3n)[endof(~t[1])+1$1-1]^t[2],factor(2n))/3

Попробуйте онлайн! Последний тест требует слишком много памяти для TIO, но я проверил это локально.

Как это устроено

Чтобы избежать ввода в специальном регистре 1 - произведение пустого словаря не определено - мы умножаем вход n на 2 и делим конечный результат на его пару 3 .

factor(2n)дает в качестве словаря все положительные показатели простых множителей 2n . При переборе словаря мы получим пары ключ-значение / простое-экспонента. Функция prodбудет принимать эти пары, применять к ним анонимную функцию t->...и возвращать произведение результатов.

Для каждой пары т = (р, е) , endof(~t[1])или endof(primes(t[1]))возврата к , число простых чисел , которые меньше или равны р , а это означает , что р является к е простое число.

+1$1-1увеличит k , XOR k + 1 с 1 и уменьшит результат. Если k нечетно, k + 1 является четным, поэтому XOR увеличивается, и окончательный результат равен k + 1 . Если k четное, k + 1 нечетное, поэтому XOR уменьшается, и в результате получается k - 1 .

Наконец, мы вычисляем все простые числа, меньшие или равные 3n, с помощью (~3n)или primes(3n)(наибольший простой множитель 2n меньше или равен n, если n> 2 , и всегда есть простое число между n и 2n ), выбираем одно с индексом k + 1 или к - 1 , и поднять его на е - й мощности с ^t[2].

Деннис
источник
2

Python 2, 112 109 108 95 94 байта

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

Проверьте это на Ideone .

Как это устроено

Когда вызывается f , сначала вычисляется 1 / n . Если результат не равен нулю, n равно 1 и f возвращает 1 .

Если n> 1 , происходит следующее.

  • Если n не делится на p [1] (изначально 2 ), n%p[1]то получится истинное значение и

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

    вызывается.

    Эта ветвь генерирует простое число, пока предпоследняя не разделит п равномерно . Для этого он использует следующее следствие из теоремы Вильсона .

    следствие теоремы Вильсона

    Во всех случаях m равен факториалу k - 1 (первоначально 6 = 3! И 4. В каждой итерации результат перед m*m%k*[k]добавлением к списку простых чисел p добавляется . По следствию m*m%kравен 1, если k простое и 0 если нет, то это добавляет k к p тогда и только тогда, когда k - простое число.

  • Если n делится на p [1] , n%p[1]получим 0 и

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

    исполняется.

    Если p содержит четное количество простых чисел, то len(p)*2%4получится 0, а первый множитель примет значение p [0] . Если p содержит нечетное количество простых чисел, len(p)*2%4получим 2, а первый множитель примет значение p [2] .

    В любом случае это простое число, показатели которого должны поменяться местами с показателем p [1] , поэтому мы делим n на p [1] (уменьшая показатель степени на 1 ) и умножаем результат f(n/p[1])на соответствующее простое число (увеличивая показатель степени на 1 ).

    Обратите внимание, что f(n/p[1])сбрасывает k , m и p к значениям по умолчанию. f(n/p[1],k,m,p)повысит эффективность за счет шести дополнительных байтов.

Деннис
источник
1

Pyth, 25 байт

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
Дрянная Монахиня
источник
1

Юлия, 155 131 127 байт

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

Это анонимная функция, которая принимает целое число и возвращает целое число. Чтобы вызвать его, присвойте его переменной. Требуется версия Julia <0.5, потому что основная функциональность была удалена из Base в 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

Попробуйте онлайн! (Включает все тестовые случаи)

Алекс А.
источник
1

На самом деле 15 байтов

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

Попробуйте онлайн!

Объяснение:

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
Mego
источник
1

05AB1E, 22 байта

Ó¾‚˜2ô€R˜DgL<Ø)øvy`smP

Разъяснения

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

Попробуйте онлайн

Emigna
источник
0

J, 21 байт

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

Получает простые показатели n как простые степени с нулями. Затем разбейте их на неперекрывающиеся подсписки размером 2, заполняя их дополнительным нулем. Затем переверните каждый подсписок и сведите их в список. Наконец, преобразовать обратно из простых показателей в число.

использование

   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
миль
источник