Codegolf — У Меня Номер «Redivosite»?

Mora

_{Redivosite — это слово-портманто, придуманное исключительно для этой задачи. Это смесь сокращения, деления и композиции.}

Определение

Учитывая целое число Н > 6:

Если Н является простым, Н не является номером повторного распределения.
Если Н является составным:
- повторно вычислять Н' = Н/д + д + 1 до Н' является простым, где д является наименьшим делителем Н больше 1
- Н является числом повторного разделения тогда и только тогда, когда окончательное значение Н' является делителем Н

Ниже приведены 100 первых номеров Redivosite (на момент публикации записей OEIS не было):

 14,42,44,49,66,70,143,153,168,169,176,195,204,260,287,294,322,350,414,462,518,553,572,575,592,629,651,702,726,735,775,806,850,869,889,891,913,950,1014,1023,1027,1071,1118,1173,1177,1197,1221,1235,1254,1260,1302,1364,1403,1430,1441,1554,1598,1610,1615,1628,1650,1673,1683,1687,1690,1703,1710,1736,1771,1840,1957,1974,2046,2067,2139,2196,2231,2254,2257,2288,2310,2318,2353,2392,2409,2432,2480,2522,2544,2635,2640,2650,2652,2684,2717,2758,2760,2784,2822,2835

Примеры

Н = 13: 13 — простое число, поэтому 13 не является числом повторного деления.
Н = 32: 32/2+3=19; 19 не является делителем или 32, поэтому 32 не является числом повторного деления.
Н = 260: 260/2+3=133, 133/7+8=27, 27/3+4=13; 13 — делитель или 260, поэтому 260 — число повторного деления.

Ваша задача

Учитывая целое число Н, верните истинное значение, если это номер повторного разделения, или ложное значение в противном случае. (Вы также можете вывести любые два различных значения, если они согласованы.)
Входные данные гарантированно будут больше, чем 6.
Это , поэтому побеждает самый короткий ответ в байтах!

#код-гольф #код-гольф #задача принятия решения #целое число #деление

Montani

Хаскель, 91 85 83 80 75 74 байта

                  iI.WtPHh+/ZKhPZK || Full program.

.W             || Functional while. It takes two functions as arguments, A and B.

|| While A(value) is truthy, turn the value into B(value). The 

|| starting value is the input.

tPH          || First function, A. Takes a single argument, H.

PH          || .. The prime factors factors of H.

t            || .. Tail (remove first element). While truthy (H is composite):

h+/ZKhPZK || The second function, B. Takes a single argument, Z:

/Z      || .. Divide Z, by:

KhP   || .. Its lowest prime factor, and assign that to K.   

h         || .. Increment. 

+      K || And add K.
iI               || Check if the result (last value) divides the input.

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

            6                                                            Push 6

0                                                           Push unused character

`                   ł                     ł      ł         Return point for all three loops

ŕ                                                         Remove top of stack

⁺                                                        Increment top of stack (n)

ĐĐ                                                      Triplicate top of stack (n)

ϼ↓                                                    Get smallest prime factor of n (returns 1 if n is prime) 

Đ                                                   Duplicate top of stack

3Ș⇹                                                Manipulate stack so that the top is (in descending order): [d,(N,N'),d]

÷+⁺                                             Calculates N'=(N,N')/d+d+1

Đṗ¬                                          Is N' not prime?

⇹⁻⇹                                       Decrement N' (so the increment at the beginning doesn't change the value), and keep the boolean on top - end of innermost loop (it loops if top of stack is true)

ŕ                                     Remove top of stack

á                                    Convert stack to array

Đ                                   Duplicate array

0⦋Đ                                Get the first element (N)

↔ĐŁ⁻⦋                           Get the last element ((final N')-1)

⁺                          Increment to get (final N')

|¬                        Does N' not divide N?

⇹Đṗ                     Is N prime?

⇹3Ș∨                 Is N prime or does N' not divide N? - end of second loop (loops if top of stack is true)

⇹Đƥ⇹ŕ           Print N, and reduce stack to [N]

1          Push garbage (pushes 1 so that the outermost loop does not terminate)

Изменить: -2 байта благодаря @BMO, -3 байта благодаря @H.PWiz и -5-6 байт благодаря @Ørjan Johansen.

Owernenendata66

Шелуха, 14 байт

60`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹Đṗ⇹3Ș∨ł⇹Đƥ⇹ŕ1ł

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

-3 спасибо H.PWiz.

Ac_troll

С (ГКК), 94 89 байт

←⁻0`ŕ⁺ĐĐϼ↓Đ3Ș⇹÷+⁺Đṗ¬⇹⁻⇹łŕáĐ0⦋Đ↔ĐŁ⁻⦋⁺|¬⇹ṗ⇹3Ș⊽

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

Объяснение

 {(⍵≤60)∨π⍵:0⋄ -- if arg ⍵ is prime or <=6 return 0

⍵{1=⍴t←π⍵:0=⍵|⍺⋄ -- if list of factors ⍵ has length 1 (it is prime)

-- then return ⍺mod⍵==0

⍺∇1+↑t+⍵÷↑t}⍵}   -- else recall this function with args ⍺ and 1+↑t+⍵÷↑t

||answer||

Желе, 14 байт

h←{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}
v←⍳100     
v,¨h¨v

1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0  10 0  11 0

12 0  13 0  14 1  15 0  16 0  17 0  18 0  19 0  20 0  

21 0  22 0  23 0  24 0  25 0  26 0  27 0  28 0  29 0  

30 0  31 0  32 0  33 0  34 0  35 0  36 0  37 0  38 0  

39 0  40 0  41 0  42 1  43 0  44 1  45 0  46 0  47 0  

48 0  49 1  50 0  51 0  52 0  53 0  54 0  55 0  56 0  

57 0  58 0  59 0  60 0  61 0  62 0  63 0  64 0  65 0  

66 1  67 0  68 0  69 0  70 1  71 0  72 0  73 0  74 0  

75 0  76 0  77 0  78 0  79 0  80 0  81 0  82 0  83 0  

84 0  85 0  86 0  87 0  88 0  89 0  90 0  91 0  92 0  

93 0  94 0  95 0  96 0  97 0  98 0  99 0  100 0

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

Как это работает

{(⍵≤6)∨0π⍵:0⋄⍵{1=⍴t←π⍵:0=⍵|⍺⋄⍺∇1+↑t+⍵÷↑t}⍵}

||answer||

Питон 2, 97 91 байт

(~: * 0 = |~)(1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Input: N

(1 + d + ] % d =. 0 { q:) ^: (0&p:) ^:_ Find the final N'

^:        ^:_  Do while

0&p:       N is not prime

q:                 Get prime factors (in order)

0 {                    Take first (smallest divisor)

d =.                        Assign this value to d

1 + d + ] %  d                           Compute (N/d) + 1 + d
(~: * 0 = |~)                                        Is it redivosite?

0 = |~                                          N = 0 (mod N'), i.e. N'|N

*                                                 And

~:                                                   N =/= N', i.e. N is not prime

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

Выводы через код выхода.

Негольфед:

_2{

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

Fegeembemia

05AB1E, 17 16 байт

^:(0&p:)

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

Объяснение

<./@q: ||answer||

Пиф, 20 байт

(~:*0=|~)(1+d+]%d=.0{q:)^:(0&p:)^:_

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

Как это работает

import StdEnv
@n#v=hd[p\\p<-[2..]|and[gcd p i<2\\i<-[2..p-1]]&&n rem p<1]
|v<n= @(n/v+v+1)=n
?n= @n<n&&n rem(@n)<1

И первые 4 байта ( (g=!PrimeQ@#&)@#&&(#//.x_/;g@x:>x/(c=Divisors[x][[2]])+c+1)\[Divides]#& ) just check if the input is not prime.

С помощью Эминья, мне удалось сохранить 3 байта.

Btnmlf5e87

Питон 3, 149 байт

use POSIX;
&r($_,$_);
sub p{

my $n=shift;

if($n<=1){

return;

}

if($n==2||$n==3){

return 1;

}

if($n%2==0||$n%3==0){

return;

}

for(5..ceil($n/2)){

if($n%$_==0){

return;

}

}

return 1;
}
sub r{

my $n=shift;

my $o=shift;

if(&p($n)){

print $o%$n==0&&$n!=$o ? 1 : 0;

last;

}

for(2..ceil($n/2)){

if($n%$_==0){

&r(($n/$_)+$_+1, $o);

last;

}

}
}

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

Использование ситового подхода. Должно быть быстро( use POSIX;&r($_,$_); sub p{$n=shift;if($n<=1){return;}if($n==2||$n==3){return 1;}if($n%2==0||$n%3==0){return;}for(5..ceil($n/2)){if($n%$_==0){return;}}return 1;} sub r{$n=shift;$o=shift;if(&p($n)){print $o%$n==0&&$n!=$o?1:0;last;}for(2..ceil($n/2)){if($n%$_==0){&r(($n/$_)+$_+1, $o);last;}}} = time complexity of the sieve of Eratosthenes) even with large j ?V©vU :ßU/(U=k g)+°UNg (но магазины 1 integers in memory)

Примечание:

Можно доказать, что все промежуточные значения 0 does not exceed {(0=n|⍵)∧⍵>n←{⍬≢k←o/⍨0=⍵|⍨o←2↓⍳⍵:∇1+d+⍵÷d←⌊/k⋄⍵}⍵} и для function r=f(n)k=n;while~isprime(k)l=2:k;d=l(~mod(k,l))(1);k=k/d+d+1;end;r=~mod(n,k)&k<n;end f n|mod(product[1..n-1]^2)n>0=1<0|1>0=n`mod`u n<1 u n|d<-[i|i<-[2..],n`mod`i<1]!!0=last$n:[u$n`div`d+d+1|d/=n] может быть в O(N log N) instead of def f(N): n=N;s=[0]*-~N for p in range(N,1,-1):s[2*p::p]=(N-p)//p*[p] while s[n]:n=n//s[n]-~s[n] return s[N]>1>N%n для просеивания.
(n // s[n]) + s[n] + 1 doesn't work, n//s[n]-~s[n] необходимо использовать из-за индекса списка.
Хранение s[q] = p into another variable doesn't help, unfortunately.

Объяснение:

s[q] == 0 == p .
Сначала массив q is initialized with p нули (Python индексирует 0, поэтому индексы s[p] == 0 )
После инициализации, s[p] < 1 is expected to be [2 .. N-1] если p is a prime, and s[1] для s[0] the minimum prime which divides n если n is a composite. p и p values are not important.
Для каждого n in range 0 :
- Если s[n] (that is, 0..N ), затем N+1 is a prime, and for each s будучи кратным N+1 and -~N , назначать range .
Последние две строки просты, за исключением того, что // == / .

Питон 3, 118 байт

range(2,N+1)

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

Ценой немного худшей производительности. (Этот работает в range(2,N) time complexity, assume reasonable implementation of Python slices)

Эквивалентная полная программа 117 байт.

Bocahsrogo

Хаскелл, 110 байт

p

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

Не очень рад...

ASLLAN

Октава, 92 байта

N > 7

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

Morovei

АПЛ (Диалог), 50 байт

N

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

Mashyta

Япт, 25 24 байта

Боюсь, я пошел в неправильном направлении, но у меня нет времени попробовать другой подход.

Выходы n for false or O(N) для правды.

N

Попробуйте это

Wlkxy8

Перл 5, 291+1(-a) = 292 байта

Черт побери Perl за отсутствие встроенной программы проверки простых чисел.

O(N log log N)

версия без гольфа,

def f(N):
	n=N;s=[0]*-~N
	for p in range(2,N):
		if s[p]<1:
			for q in range(p*p,N+1,p):s[q]=s[q]or p
	while s[n]:n=n//s[n]-~s[n]
	return s[N]>1>N%n

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

Easeltlex

Язык Wolfram (Математика), 64 байта

Простая реализация с использованием рекурсивной замены шаблонов

(замена «\[Divides]» на символ «∣» экономит 7 байт)

<P_Q

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

Zidvdwmyd69

Чистый, 128 117 114 байт

<P_QiI.WtPHh+/ZKhPZK

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

Aleksandr.vav

Дж, 35 байт

[                  # start loop

Dp#               # break if current value is prime

Ò              # get prime factors of current value

ć©            # extract the smallest (d) and store a copy in register

sP          # take the product of the rest of the factors

+>        # add the smallest (d) and increment

]       # end loop

Ö      # check if the input is divisible by the resulting prime

®p    # check if the last (d) is prime (true for all composite input)

*   # multiply

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

Минимальный делитель, являющийся первым простым множителем, был украден из решения @Dennis's Jelly (ранее я использовал [Dp#Òć©sP+>]Ö®p* ).

Должен быть лучший способ выполнить итерацию, но я не могу его найти. Я думал не делать тест на простоту ( r = 0 # r is the lowest divisor of the current number, # initialized to 0 for the while loop condition. e = d = i = input() # d remains unchanged, e is the current number # and i is the next number. while r != e: # If the number is equal to its lowest divisor, # it is prime and we need to end the loop. e = i # current number := next number r = [j for j in range(2, i+1) # List all divisors of the number in the range [2; number + 1) if i%j < 1][0] # and take the first (lowest) one. i = i/r+r+1 # Calculate the next number. # We now arrived at a prime number. print d%e == 0 and d != e # Print True if our current number divides the input # and is distinct from the input. # If our current number is equal to the input, # the input is prime. ) and instead using adverse but it seems like that will be a bit longer since you'll need a r=0;e=d=i=input() while r-e:e=i;r=[j for j in range(2,i+1)if i%j<1][0];i=i/r-~r d%e<1<d/e<q и некоторые изменения, которые могут не привести к чистому сокращению.

Я действительно чувствую, что должен быть способ избежать использования скобок при проверке простоты.

Пояснение (расширенное)

ÆḌḊ         Helper link. Argument: k

ÆḌ          Yield k's proper (including 1, but not k) divisors.

Ḋ         Dequeue; remove the first element (1).

Ç.ịS‘µÇ¿eÇ  Main link. Argument: n

µ      Combine the links to the left into a chain.

Ç¿    While the helper link, called with argument n, returns a truthy result,

i.e., while n is composite, call the chain to the left and update n.
Ç             Call the helper link.

.ị           At-index 0.5; return the elements at indices 0 (last) and 1 (first).

This yields [n/d, d].

S          Take the sum.

‘         Increment.

Ç   Call the helper link on the original value of n.

e    Test if the result of the while loop belongs to the proper divisors.

||answer||

APL NARS, 43 символа, 85 байт

ÆḌḊ
Ç.ịS‘µÇ¿eÇ

(надеясь, что он сходится для всех чисел>6) тест:

m,n;                  // two global integers
o(k){                 // determine k's smallest divisor

for(m=1;m++<k;)      // loop through integers 2 to n (inclusive)

if(k%m<1)return m;} // return found divisor
F(N){                 // determine N's redivosity

for(n=N;             // save N's initial value

m=o(n),             // calculate n's smallest divisor (no name clash regarding m)

m-n;                // loop while o(n)!=n, meaning n is not prime

//  (if N was prime, the loop will never be entered)

n=n/m-~m);          // redivosite procedure, empty loop body

N=m<N>N%n;}          // m<N evaluates to 0 or 1 depending on N being prime,

//  N%n==0 determines whether or not N is divisible by n,

//  meaning N could be redivosite => m<N&&N%n==0

//  <=> m<N&&N%n<1 <=> m<N&&1>N%n <=> (m<N)>N%n <=> m<N>N%n

Идея использования двух анонимных функций пришла мне в другое решение Apl.

m,n;o(k){for(m=1;m++<k;)if(k%m<1)return m;}
F(N){for(n=N;m=o(n),m-n;n=n/m-~m);N=m<N>N%n;}

||answer||

Пит, 44 байты

э¬Ṡ¦ΩṗoΓ~+→Πpṗ

Объяснение см. в приведенном ниже коде. Единственные различия заключаются в том, что (1) перед этим N уменьшается на единицу, чтобы учесть приращение в начале цикла, и (2) вместо ИЛИ используется NOR.

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

Я сделал это до того, как перечитал вопрос и заметил, что ему нужно только истинное/ложное значение.

Пыть, 52 байта

f x=x#x                           -- call # with x for both parameters
n#m               

|d<-[2..m-1],mod m d<1   -- for all divisors d of m

[n#(div m d+d+1)           ]  -- make a list of recursive calls to #,

-- but with m set to m/d+d+1

++ [mod n m<1&&m<n]            -- append the Redivosite-ness of n (m divides n,

-- but is not equal to n)

!!0    -- pick the last element of the list

-- -> if there's no d, i.e. m is prime, the

--    Redivosite value is picked, else the

--    result of the call to # with the smallest d

Печатает бесконечный список номеров Redivosite.

Объяснение:

n#m=([n#(div m d+d+1)|d<-[2..m-1],mod m d<1]++[mod n m<1&&m<n])!!0
f x=x#x

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

Похожие темы	Дата
Авторегистратор gmail 2 (обновление 2.0)	19.12.2024, 05:12
Нужны ваши предложения и советы	19.12.2024, 05:12
Codegolf - Точка Гонится За Мной!	19.12.2024, 05:12
Codegolf - Имитация Нажатий Клавиш	19.12.2024, 05:12
Codegolf — Объединение Строк С Контекстом	19.12.2024, 05:12
Codegolf - Какой Степени Этот Палиндром?	19.12.2024, 05:12
Codegolf - Какой У Меня Ip-Адрес?	19.12.2024, 05:12
Codegolf - Рок Круглосуточно	19.12.2024, 05:12
Codegolf - Идеальные Радикалы	19.12.2024, 05:12
Codegolf - "99 Бутылок Пива"	19.12.2024, 05:12

Codegolf — У Меня Номер «Redivosite»?

Определение

Примеры

Ваша задача

Хаскель, 91 85 83 80 75 74 байта

Шелуха, 14 байт

С (ГКК), 94 89 байт

Объяснение

Желе, 14 байт

Как это работает

Питон 2, 97 91 байт

Негольфед:

05AB1E, 17 16 байт

Пиф, 20 байт

Как это работает

Питон 3, 149 байт

Питон 3, 118 байт

Хаскелл, 110 байт

Октава, 92 байта

АПЛ (Диалог), 50 байт

Япт, 25 24 байта

Перл 5, 291+1(-a) = 292 байта

Язык Wolfram (Математика), 64 байта

Чистый, 128 117 114 байт

Дж, 35 байт

Пояснение (расширенное)

APL NARS, 43 символа, 85 байт

Пит, 44 байты

Пыть, 52 байта

Интересно