Мне задали этот вопрос в интервью, но я не смог найти никакого решения. Я не знаю, был ли вопрос прав или нет. Я много пробовал, но не смог найти решение. Честно говоря, ничего не пришло мне в голову.

Рокко номера

Целое положительное число является числом Рокко, если оно может быть представлено в виде или , где - простое число.$n$$n=p(p+14)$$n=p(p-14)$$p$

Первые 10 чисел Рокко:

задача

Ваш код должен принять положительное целое число в качестве входных данных и определить, является ли это число Рокко или нет.

Брауни очки

• Напишите функцию, которая вычисляет и печатает число чисел Рокко, меньшее или равное 1 миллиону.
• Напишите функцию, которая вычисляет и печатает количество чисел Рокко из бонусного вопроса (выше одного), которые являются простыми.

05AB1E , 8 байтов

Возвращает $1$ если $n$ - число Рокко, или $0$ противном случае.

fDŠ/α14å

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

Как?

Учитывая положительное целое число $n$ , мы проверяем, существует ли простой фактор $p$ числа $n$ такой, что:

комментарии

fDŠ/α14å  # expects a positive integer n as input       e.g. 2655
f         # push the list of unique prime factors of n  -->  2655, [ 3, 5, 59 ]
 D        # duplicate it                                -->  2655, [ 3, 5, 59 ], [ 3, 5, 59 ]
  Š       # moves the input n between the two lists     -->  [ 3, 5, 59 ], 2655, [ 3, 5, 59 ]
   /      # divide n by each prime factor               -->  [ 3, 5, 59 ], [ 885, 531, 45 ]
    α     # compute the absolute differences
          # between both remaining lists                -->  [ 882, 526, 14 ]
     14å  # does 14 appear in there?                    -->  1

JavaScript (ES7), 55 байт

n=>(g=k=>k>0&&n%--k?g(k):k==1)(n=(49+n)**.5-7)|g(n+=14)

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

Как?

Учитывая положительное целое число $n$ , мы ищем такое простое число $x$ , что $x(x+14)=n$ или $x(x-14)=n$ .

Отсюда и следующие квадратные уравнения:

Положительный корень $(1)$ :

$(2)$

$x_0$$x_1$

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

g = k =>    // k = explicit input; this is the divisor
            // we assume that the implicit input n is equal to k on the initial call
  k > 0 &&  // abort if k is negative, which may happen if n is irrational
  n % --k ? // decrement k; if k is not a divisor of n:
    g(k)    //   do a recursive call
  :         // else:
    k == 1  //   returns true if k is equal to 1 (n is prime)
            //   or false otherwise (n is either irrational or a composite integer)

Основная функция обертки:

n => g(n = (49 + n) ** .5 - 7) | g(n += 14)

Perl 6 , 45 28 байт

((*+49)**.5+(7|-7)).is-prime

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

$\sqrt{n+49}\pm7$$n$

Объяснение:

 (*+49)**.5                   # Is the sqrt of input+49
           +(7|-7)            # Plus or minus 7
(                 ).is-prime  # Prime?

Регулярное выражение (ECMAScript), 64 62 байта

$a$$a+14$$n=a(a+14)$$a$$a+14$

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

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

^(?=(x((x{14})(x+)))(?=(\1*)\4\2*$)(\1*$\5))\6\3?(?!(xx+)\7+$)

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

 # For the purposes of these comments, the input number = N.
 ^
 # Find two numbers A and A+14 such that A*(A+14)==N.
 (?=
     (x((x{14})(x+)))   # \1 = A+14; \2 = \1-1; \3 = 14; \4 = A-1; tail -= \1
     (?=                # Assert that \1 * (\4+1) == N.
         (\1*)\4\2*$    # We are asserting that N is the smallest number satisfying
                        # two moduli, thus proving it is the product of A and A+14
                        # via the Chinese Remainder Theorem. The (\1*) has the effect
                        # of testing every value that satisfies the "≡0 mod \1"
                        # modulus, starting with the smallest (zero), against "\4\2*$",
                        # to see if it also satisfies the "≡\4 mod \2" modulus; if any
                        # smaller number satisfied both moduli, (\1*) would capture a
                        # nonzero value in \5. Note that this actually finds the
                        # product of \4*\1, not (\4+1)*\1 which what we actually want,
                        # but this is fine, because we already subtracted \1 and thus
                        # \4*\1 is the value of tail at the start of this lookahead.
                        # This implementation of multiplication is very efficient
                        # golf-wise, but slow, because if the number being tested is
                        # not even divisible by \1, the entire test done inside this
                        # lookahead is invalid, and the "\1*$" test below will only
                        # fail after this useless test has finished.
     )
     (\1*$\5)           # Assert that the above test proved \1*(\4+1)==N, by
                        # asserting that tail is divisible by \1 and that \5==0;
                        # \6 = tool to make tail = \1
 )
 # Assert that either A or A+14 is prime.
 \6                     # tail = \1 == A+14
 \3?                    # optionally make tail = A
 (?!(xx+)\7+$)          # Assert tail is prime. We don't need to exclude treating
                        # 1 as prime, because the potential false positive of N==15
                        # is already excluded by requiring \4 >= 1.
 

Брахилог , 13 12 байт

ṗ;14{+|-};?×

Введите номер кандидата в качестве аргумента командной строки. Выходы trueили false. Попробуйте онлайн!

объяснение

Код - это предикат, входные данные которого не ограничены, а выходные данные - число, которое мы тестируем.

ṗ             Let the input ? be a prime number
 ;14          Pair it with 14, yielding the list [?, 14]
    {+|-}     Either add or subtract, yielding ?+14 or ?-14
         ;?   Pair the result with the input, yielding [?+14, ?] or [?-14, ?]
           ×  Multiply; the result must match the candidate number

(Советы приветствуются. Это {+|-}все еще кажется неуклюжим.)

Брахилог , 9 байт

Различный подход тогда DLosc «s ответ

Ċ-14&∋ṗ&×

Принимает N в качестве выходных данных, возвращает [P, P-14] или [P + 14, P] обратно через вход (наибольшее число сначала)

объяснение

Ċ              # The 'input' is a pair of numbers
 -14           #   where the 2nd is 14 smaller then the first
    &∋ṗ        #   and the pair contains a prime
       &×      #   and the numbers multiplied give the output (N)

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

Pyth, 22 20 байт

}Qsm*Ld+Ld_B14fP_TSh

Попробуйте это онлайн здесь .

}Qsm*Ld+Ld_B14fP_TShQ   Implicit: Q=eval(input())
                        Trailing Q inferred
                  ShQ   Range [1-(Q+1)]
              fP_T      Filter the above to keep primes
   m                    Map the elements of the above, as d, using:
          _B14            [14, -14]
       +Ld                Add d to each
    *Ld                   Multiply each by d
  s                     Flatten result of map
}Q                      Is Q in the above? Implicit print

Редактировать: сохраненные 3 байта в качестве входных данных всегда будут положительными, поэтому нет необходимости отфильтровывать отрицательные значения из списка. Также исправлена ​​ошибка для входных данных 1и 2стоимостью 1 байт. Предыдущая версия:}Qsm*Ld>#0+Ld_B14fP_TU

05AB1E , 16 15 14 байтов

Сохранено 1 байт путем вычисления 14 7·вместо žvÍ(не могу поверить, что я вообще не думал об этом).

Сохранено 1 байт благодаря Emigna

ÅPε7·D(‚+y*Q}Z

Попробуйте онлайн! или проверить все входы

объяснение

                 # Implicit input n
ÅP               # Push a list of primes up to n
  ε         }    # For each prime in the list...
   7·            # Push 14 (by doubling 7)
     D(‚         # Push -14 and pair them together to get [14,-14]
        +        # Add [14,-14] to the prime
         y*      # Multiply the prime to compute p(p-14) and p(p+14)
           Q     # Check if the (implicit) input is equal to each element
             Z   # Take the maximum

J , 21 15 байт

На основании решения Арно

14 e.q:|@-(%q:)

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

Предыдущая попытка:

e.&,14&(]*+,-~)@p:@i.

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

Сетчатка 0.8.2 , 61 байт

.+
$*
^((1{14})1(1)+)(?<=(?<!^\4+(..+))\2?)(?<-3>\1)+$(?(3)1)

Попробуйте онлайн! Объяснение:

.+
$*

Преобразовать в одинарный.

^((1{14})1(1)+)

\1захватывает больший из двух факторов. \2захватывает константу 14, сохраняя байт. \3захватывает меньший из двух факторов, минус 1. Это также гарантирует, что оба фактора, по крайней мере, 2.

(?<=(?<!^\4+(..+))\2?)

Проверьте два фактора, чтобы убедиться, что хотя бы один из них является простым. Идея использования \2?была бесстыдно украдена из ответа @ Deadcode.

(?<-3>\1)+

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

$(?(3)1)

Убедитесь, что продукт равен указанному числу.

Прямой перевод в Retina 1 путем замены $*на *1будет иметь тот же счетчик байтов, но можно сохранить байт, заменив все 1s на _s, а затем *1можно заменить на *вместо *_. Предыдущая Retina 1 ответ за 68 байт:

.+
*
Lw$`^(__+)(?=(\1)+$)
$1 _$#2*
Am` (__+)\1+$
(_+) \1

0m`^_{14}$

Попробуйте онлайн! Объяснение:

.+
*

Преобразовать в одинарный.

Lw$`^(__+)(?=(\1)+$)
$1 _$#2*

Найти все пары факторов.

Am` (__+)\1+$

Убедитесь, что один прост.

(_+) \1

Возьми абсолютную разницу.

0m`^_{14}$

Проверьте, есть ли 14.

JavaScript (Babel Node) , 69 байт

Блин, хотя я собирался обыграть ответ Арно, но нет .....: c

x=>[...Array(x)].some((a,b)=>x/(a=(p=n=>--b-1?n%b&&p(n):n)(b))-a==14)

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

Я хочу избавиться от x=>[...Array(x)].some(части, используя рекурсию, чтобы она могла стать короче со временем

объяснение

x=>[...Array(x)]                                                              Creates a range from 0 to x-1 and map:

                .some((a,b)=>                                                 Returns True if any of the following values is true
                             x/                                              Input number divided by
                                (a=(p=n=>--b-1?n%b&&p(n):n)(b))               recursive helper function. Receives a number (mapped value) as parameters and returns 
                                                                              the same number if it is prime, otherwise returns 1. Take this value
                                                                              and assign to variable a
                                                               -a            Subtract a from the result  
                                                                     ==14    Compare result equal to 14

Использует формулу

Japt , 10 байт

То же, что мой ответ на Javascript

k d@/X-X¥E

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

Желе , 9 байт

:ạ⁹ɗÆf14e

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

APL (NARS) 16 символов, 32 байта

{14=∣r-⍵÷r←↑⌽π⍵}

{π⍵} нашел бы факторизацию своего аргумента, и мы предполагаем, что последний элемент его результата (список делителей n) является максимальным простым делителем n; Здесь мы предполагаем, что одно эквивалентное определение числа Рокко: n - это число Рокко <=>, максимальное простое число множителя n: r таково, что оно истинно 14 = ∣rn ÷ r [для псевдокода C как 14 == abs (rn) / r) это определение числа Рокко кажется приемлемым в конце концов в диапазоне 1..1000000]; диапазон значения ok будет 1..maxInt; тестовое задание:

 f←{14=∣r-⍵÷r←↑⌽π⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨1..10000
32  51  95  147  207  275  351  435  527  627  851  1107  1247  1395  1551  1887  2067  2255  2451  2655  2867  3551  4047  4307  4575  5135  5427  5727  6035  6351  6675  7347  8051  8787  9167  9951   

C # (интерактивный компилятор Visual C #) , 99 байт

n=>Enumerable.Range(2,n).Any(p=>Enumerable.Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

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

Enumerable.Range поражает снова :) Используя сумасшедший флаг компилятора, вы можете немного уменьшить ситуацию, хотя я являюсь фанатом ванильного решения.

C # (интерактивный компилятор Visual C #) + /u:System.Linq.Enumerable, 77 байт

n=>Range(2,n).Any(p=>Range(2,p).All(y=>y>=p|p%y>0)&(n==p*(p+14)|n==p*(p-14)))

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

Ниже приведен порт решения Арно, который выглядел довольно круто. В настоящее время он самый длинный, но, возможно, его можно сыграть в гольф.

C # (интерактивный компилятор Visual C #) , 101 байт

n=>{bool g(int k)=>--k<2?n>1:n%k>0&g(k);var d=Math.Sqrt(n+49)-7;return(n=(int)d)==d&(g(n)|g(n+=14));}

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

APL (NARS) 30 символов, 60 байтов

{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}

Здесь 0π - функция, скажем, если одно число является простым, test:

 f←{∨/{0=1∣⍵:0π⍵⋄0}¨(7,¯7)+√49+⍵}
 {⍞←{1=f ⍵:' ',⍵⋄⍬}⍵⋄⍬}¨0..700
32  51  95  147  207  275  351  435  527  627

F #, 2 ответа (неконкурентный)

Мне очень понравились ответы @Arnauld, поэтому я перевел их.

123 байта , основываясь на ответе JavaScript

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||)

Объяснение:

fun n->let t=int<|sqrt(float n+49.)in Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)[t-7;t+7]|>Seq.reduce(||) //Lambda which takes an integer, n
       let t=int<|sqrt(float n+49.)                                                                                         //let t be n, converted to float, add 49 and get square root, converted back to int (F# type restrictions)
                                   in                                                                                       //in the following...
                                                                                                  [t-7;t+7]                 //Subtract and add 7 to t in a list of 2 results (Lists and Seqs can be interchanged various places)
                                      Seq.map(fun n->Seq.filter(fun i->n%i=0)[1..n]|>Seq.length=2)                          //See if either are prime (here, if either result has 2 and only 2 divisors)
                                                                                                           |>Seq.reduce(||) //And logically OR the resulting sequence

125 байтов , основанный на ответе 05AB1E

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14

Объяснение:

fun n->let l=Seq.filter(fun i->n%i=0)[2..n-1]in let m=Seq.map(fun i->n/i)l in Seq.map2(fun a b->abs(a-b))l m|>Seq.contains 14  //Lambda which takes an integer, n
       let l=Seq.filter(fun i->n%i=0)[2..n-1]                                                                                  //let l be the list of n's primes 
                                             in                                                                                //in...
                                                let m=Seq.map(fun i->n/i)l                                                     //m, which is n divided by each of l's contents
                                                                           in                                                  //and then...
                                                                              Seq.map2(fun a b->abs(a-b))l m                   //take the absolute difference between each pair of items in the two sequences to make a new sequence
                                                                                                            |>Seq.contains 14  //and does the resulting sequence contain the number 14?

Python 2 , 58 байт

Выходы по коду выхода, fails ( 1) для чисел Рокко.

P=k=1.
n=input()
exec"P*=k*k;k+=1;P%k*abs(n/k-k)==14>y;"*n

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