_{(через чат )}

Запись OEIS A123321 перечисляет последовательность чисел, которые являются произведением семи различных простых чисел. Для краткости мы назовем этот номер 7DP . Первые несколько чисел и соответствующие им делители приведены ниже:

510510 = 2 * 3 * 5 * 7 * 11 * 13 * 17
570570 = 2 * 3 * 5 * 7 * 11 * 13 * 19
690690 = 2 * 3 * 5 * 7 * 11 * 13 * 23
746130 = 2 * 3 * 5 * 7 * 11 * 17 * 19

Задача здесь состоит в том, чтобы найти ближайший номер 7DP, с точки зрения абсолютного расстояния, от заданного входа.

вход

Одно положительное целое число n в любом удобном формате .

Выход

Ближайший номер 7DP к n , опять же в любом удобном формате. Если два числа 7DP связаны для ближайшего, вы можете вывести одно или оба.

правила

• Можно предположить, что числа соответствуют [int]типу данных вашего языка по умолчанию (или эквивалентному).
• Либо полная программа или функция приемлемы.
• Стандартные лазейки запрещены.
• Это код-гольф , поэтому применяются все обычные правила игры в гольф, и выигрывает самый короткий код.

Примеры

5 -> 510510
860782 -> 870870
1425060 -> 1438710 (or 1411410, or both)

Python, 89 86 85 байт

f=lambda n,k=0:126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))and f(n+k,k%2*2+~k)or n

Алгоритм для начала O (страшный), и рекурсия на самом деле не помогает, но работает хорошо, если n достаточно близко к числу 7DP.

Спасибо @xnor за 3 байта!

Проверьте это на repl.it .

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

Python не имеет встроенных функций первичности или факторизации, но мы можем идентифицировать числа 7DP по количеству и характеру их делителей.

По принципу умножения число делителей целого числа может быть вычислено как произведение приращенных показателей его простой факторизации. Таким образом, σ ₀ (n) ( функция делителя ) равна 2 ^m всякий раз, когда n является числом mDP.

σ ₀ (N) = 128 , таким образом , является необходимым условием, но это не является достаточным; например, сг ₀ (2 ¹²⁷ ) = 128 , а 2 ¹²⁷ явно не число 7DP. Однако, если оба σ ₀ (N) = 128 и не идеальный квадрат делит п равномерно, то п является числом 7DP.

Для ввода n алгоритм состоит в проверке целых чисел n , n - 1 , n + 1 , n - 2 , n + 2 и т. Д. И возвращении первого числа, которое является числом 7DP.

Когда f вызывается с аргументом n , происходит следующее:

• Код

  126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))

  проверяет , не является ли n числом 7DP, следующим образом.

  Для всех целых чисел i таких, что 1 <i <n , 1>>n%i<<7*(n/i%i<1)вычисляется.

  • Если п делится на I , но не я ² , 1>>n%iвыходы 1 и (n/i%i<1)выходами 0 , в результате чего
    1 · 2 ^{7 · 0} = 1 .

  • Если n делится на i ² , 1>>n%iи (n/i%i<1)оба дают 1 , что приводит к 1 · 2 ^{7 · 1} = 128 .

  • Если n не делится на i , 1>>n%iвыдает 0 , что приводит к 0 · 2 ^{7 · x} = 0 .

  
  Сумма полученных чисел будет 2 ^м - 2 , если п представляет собой число MDP (его 2 ^м делители, за исключением 1 и п ) и число больше 127 , если п имеет идеальный квадрат фактор. Таким образом, сумма будет 126 тогда и только тогда, когда n является числом 7DP.

• Для чисел 7DP, сумма 126 , поэтому XORing его с 126 выходами 0 , который является falsy. Таким образом, выполняется лямбда или часть ля, и f возвращает текущее значение n .

• Если n не является числом 7DP, XOR вернет ненулевое истинное значение. Таким образом, и часть лямбда выполняется.

  f(n+k,k%2*2+~k)

  рекурсивно вызывает f с обновленными значениями n (следующего потенциального числа 7DP) и k (разницы между новым кандидатом и последующим).

  Если к четное, неотрицательное целое число, k%2*2дает 0 и ~kвыходы - (K + 1) . Сумма обоих результатов равна - (k + 1) , которая является нечетным, отрицательным целым числом, которое на 1 больше по абсолютной величине, чем k .

  Если к нечетное, отрицательное целое число, k%2*2дает 2 и ~kвыходы - (K + 1) . Сумма обоих результатов равна 2 - (k + 1) = - (k - 1) , что является четным неотрицательным целым числом, которое на 1 единицу больше по абсолютной величине, чем k .

  Это означает, что k принимает значения 0, -1, 2, -3, 4, ⋯ .

  Когда кумулятивно добавлено к n ₀ (начальное значение n ), результирующие целые числа

  • n ₀ + 0
  • ( n ₀ + 0) - 1 = n ₀ - 1
  • ( n ₀ - 1) + 2 = n ₀ + 1
  • ( n ₀ + 1) - 3 = n ₀ - 2
  • ( n ₀ - 2) + 4 = n ₀ + 2
  • и т.п.

  
  убедившись , что первый номер 7DP мы сталкиваемся как можно ближе к п ₀ , как это возможно.

Брахилог , 44 40 16 байт

_{Вычеркнуто 44 все еще регулярно 44; (}

:I=+.>0,.$pPdPl7

Пример:

?- run_from_atom(':I=+.>0,.$pPdPl7',1425060,Z).
Z = 1438710 .

Может ли быть так, что этот язык не всегда сосет? Я победил Желе и МАТЛ!

Тестовый пример с 5самым длинным и занимает около 10 секунд на моей машине.

Это было бы 12 байтов, если бы $pне было ошибок (нам не нужна >0,.часть)

объяснение

Brachylog по умолчанию использует программирование логики ограничений для всей целочисленной арифметики. Более того, встроенная маркировка =работает на возможно бесконечных доменах.

Она последовательно объединяет переменную с какими - либо ограничений (например , в (-inf, inf)) , как , например: 0, 1, -1, 2, -2, 3, ….

Следовательно, мы можем получить ближайший номер 7DP, посмотрев на первое число, Iобъединенное в (-inf, inf)(с использованием автоматического возврата), для которого Input + Iэто число 7DP.

:I=                Label variables in [Input, I]. I has no constraints and Input is known
   +.              Unify Output with Input + I
     >0,           Output > 0 (wouldn't be needed if $p failed for numbers less than 1)
        .$pP       Unify P with the list of prime factors of Output
            dP     Check that P with duplicates removed is still P
              l7   Check that the length of P is 7

Желе, 17 байт

Pµạ³,
×⁹ÆRœc7Ç€ṂṪ

Работает в теории, но занимает много лет.

Вот версия, которая на самом деле работает для заданных входов, но теоретически не работает для больших входов:

Pµạ³,
50ÆRœc7Ç€ṂṪ

Попробуй это здесь. Это генерирует все простые числа до 50, затем находит все 7 комбинаций простых чисел в этом списке, а затем все их произведения. Наконец, он просто находит ближайший элемент из этого списка к данному аргументу.

Конечно, как только наши 7DP содержат простые числа больше 50, это не получится. Теоретическая версия генерирует все простые числа до 256n для входа n , но в остальном работает аналогично.

доказательство

Позвольте p(x)обозначить следующий штрих после x. (Очень слабая) верхняя граница для ближайшего продукта 7DP к x:

p(x) * p(p(x)) * p(p(p(x))) * ... * p(p(p(p(p(p(p(x)))))))

Таким образом, нам нужно проверить только простые числа в [2… p (p (p (p (p (p (p (x))))))) . Постулат Бертрана говорит, что p (x) ≤ 2x , поэтому достаточно проверить все простые числа до 128x .

MATL , 21 17 16 14 13 байт

Спасибо Деннису за предложение, которое удалило 4 байта, и еще одно, которое спасло еще 1 байт!

t17*Zq7XN!pYk

Это работает в теории, но не хватает памяти для входных данных выше 6(онлайн-компилятор).

Более эффективная версия использует 21 байт и вычисляет все тестовые случаи примерно за одну секунду:

t3e4/k16+_YqZq7XN!pYk

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

• Неэффективная память
• Версия с эффективным использованием памяти
• Версия с эффективным использованием памяти, все тесты

объяснение

Версия с эффективным использованием памяти

Возьмем вход N = 860782в качестве примера. Достаточно рассмотреть простые числа до М = 29, который является первым премьером , который умножается на 2*3*5*7*11*13превышаете N . В этом примере 2*3*5*7*11*13*29 = 870870. Следующий штрих есть 31. Любой продукт, включающий это простое число или больше, будет по крайней мере2*3*5*7*11*13*31 = 930930 , и поэтому он гарантированно не будет решением, поскольку оно превышает 870870которых превышает N .

М вычисляется как первое простое число больше, чем max(N/(2*3*5*7*11*13), 16). maxФункция используется для обеспечения того , чтобы , по меньшей мере 17определена. Чтобы сохранить несколько байтов, код заменяет2*3*5*7*11*13 = 30030 на 30000, а функция maxдобавляется. Эти изменения действительны, потому что они дают большее значение.

t      % Take input implicitly. Duplicate
3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime
Zq     % Prime numbers up to that value
7XN    % Combinations of those primes taken 7 at a time. Gives a 2D array
       % with each combination on a different row
!p     % Product of each row
Yk     % Output product that is closest to the input. Implicitly display

Неэффективная память

Для дальнейшего уменьшения количества байтов разделение может быть удалено; на самом деле, достаточно умножить на 17(спасибо, @Dennis). Это гарантирует включение следующего простого числа (согласно постулату Бертрана ) и, по крайней мере, результат 17. Это работает в теории, но не хватает памяти для входов больше, чем примерно 6.

В коде раздел

3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime

заменяется

17*    % Multiply by 17

Пайк, 32 байта

#PDl 7q.ID}lRlqi*(#)DF-X,)R],She

Попробуй это здесь!

Обратите внимание, что это не работает в Интернете - время ожидания истекло. Эта версия проверяет только 2 простых числа и должна работать быстрее. Когда есть 2 числа на одинаковом расстоянии от цели, выбирается нижнее.

Это проходит через все числа, пока не найдет тот, который больше, чем вход и 7DP. Для каждого числа он избавляется от него, если это не 7DP. Затем у него есть список из 7 точек до входного с одним, который больше. Затем он выбирает тот, который ближе всего к входу.

Юлия, 59 байт

!n=sort(map(prod,combinations(17n|>primes,7))-n,by=abs)[]+n

Это очень неэффективно, но работает для первого теста на практике и для других в теории.

При стоимости еще 5 байтов - всего 64 байта - эффективность может быть значительно улучшена.

!n=sort(map(prod,combinations(n>>14+17|>primes,7))-n,by=abs)[]+n

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

Фон

Как упоминалось в ответе @ LuisMendo , набор простых чисел, которые мы должны рассмотреть для ближайшего числа 7DP, довольно мал. Достаточно, чтобы набор содержал число 7DP, которое больше, чем вход n , что будет истинно тогда и только тогда, когда он содержит простое число p ≥ 17, такое что 30300p = 2 · 3 · 5 · 7 · 11 · 13 · p ≥ п .

В интервале On, содержащем хотя бы одно простое число, доказывается, что интервал [x, 1.5x) содержит хотя бы одно простое число всякий раз, когда x ≥ 8 . Поскольку 30030/16384 ≈ 1,83 , это означает, что должно быть простое число p в (n / 30030, n / 16384) всякий раз, когда n> 8 · 30300 = 242400 .

Наконец, когда n <510510 , p = 17 явно достаточно, поэтому нам нужно учитывать только простые числа до n / 16384 + 17 .

За счет эффективности мы можем рассмотреть простые числа до 17n вместо этого. Это работает, когда n = 1 и значительно больше, чем n / 16384 + 17 для больших значений n .

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

17n|>primesи n>>14+17|>primes(битовое смещение эквивалентно делению на 2 ¹⁴ = 16384 ) вычислить простые диапазоны, упомянутые в предыдущем абзаце. Затем combinations(...,7)вычисляет все массивы из семи различных простых чисел в этом диапазоне и сопоставляет prodих, вычисляя их произведения, то есть числа 7DP, из которых мы выберем ответ.

Затем -nвычитает n Prom для каждого числа 7DP, затем sort(...,by=abs)сортирует эти различия по абсолютным значениям. Наконец, мы выбираем первое различие с помощью []и вычисляем соответствующее число 7DP, добавляя n с помощью +n.

Pyth, 30 байт

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

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

Тестирование.

(5 занимает слишком много времени, чтобы бежать)

объяснение

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

L&{IPbq7lPb     Defines a function y, whose argument is b:
 &                  Return if both the following are true:
  {IPb                  the prime factorization contains no duplicate; and:
      q7lPb             the number of prime factors is 7

           y#.W!syMH,hhZa0teZ,   The main programme. Input as Q.
                             ,QQ Implicit arguments, yield [Q,Q].
             .W                  While
               !syMH                   both numbers do not satisfy y:
                    ,hhZ             increment the first number
                          teZ        and decrement the second number
                        a0           while making it non-negative.

Mathematica 136 80 75 байт

Это простой подход, работающий вне n.

nявляется 7-значным простым продуктом, если число простых факторов равно 7 ( PrimeNu@#==7), и ни один из этих факторов не встречается более одного раза ( SquareFreeQ@#&).

g@n_:=(k=1;While[!(PrimeNu@#==7&&SquareFreeQ@#&)⌊z=n-⌊k/2](-1)^k⌋,k++];z)

Мое раннее представление (136 байт) нашло и первый продукт с 7 отличными простыми числами выше, nи, если оно существует, первый продукт с 7 отличными простыми числами ниже n. Затем он просто определил, что было ближе к n. Если продукты были равноудалены, то возвращались оба.

Текущая версия проверяет n-1, n + 1, n-2, n + 2 ... до тех пор, пока не достигнет первого 7-значного простого произведения. Эта более эффективная версия принимает подход Дениса.

Ключевое продвижение было в использовании, ⌊k/2](-1)^k⌋чтобы возвратить ряды, 0, 1, -1, 2, -2 ... Ноль используется, чтобы проверить, nявляется ли сам продукт 7-отличным от простого. По этой причине Floor(то есть ⌊...⌋) используется вместо Ceiling.

g[5]
g[860782]
g[1425060]

510510

870870

1438710

05AB1E , 10 байтов

°Åp7.ÆPs.x

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

Пытается выполнить все комбинации из 7 первых 10 ** простых чисел. Недостаточно памяти для входов больше 1.

Значительно более эффективная 14-байтовая версия:

5°/7+Åp7.ÆPs.x

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

Используются первые (входные / 100000 + 7) простые числа.