26
\$\begingroup\$

Redivosite is a portmanteau word invented for the sole purpose of this challenge. It's a mix of Reduction, Division and Composite.

Definition

Given an integer N > 6:

  • If N is prime, N is not a Redivosite Number.
  • If N is composite:
    • repeatedly compute N' = N / d + d + 1 until N' is prime, where d is the smallest divisor of N greater than 1
    • N is a Redivosite Number if and only if the final value of N' is a divisor of N

Below are the 100 first Redivosite Numbers (no OEIS entry at the time of posting):

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

Examples

  • N = 13: 13 is prime, so 13 is not a Redivosite Number
  • N = 32: 32 / 2 + 3 = 19; 19 is not a divisor or 32, so 32 is not a Redivosite Number
  • N = 260: 260 / 2 + 3 = 133, 133 / 7 + 8 = 27, 27 / 3 + 4 = 13; 13 is a divisor or 260, so 260 is a Redivosite Number

Your task

  • Given an integer N, return a truthy value if it's a Redivosite Number or a falsy value otherwise. (You may also output any two distinct values, as long as they're consistent.)
  • The input is guaranteed to be larger than 6.
  • This is , so the shortest answer in bytes wins!
\$\endgroup\$
  • 13
    \$\begingroup\$ I really wish all of these "number sequence" challenges that are just sequences of numbers with a certain property would just be asked as decision problems. I highly doubt there's any way to generate these directly, so the only possible solution is to solve the decision problem and then wrap it in a loop that finds the Nth or the first N or all integers that satisfy this property. \$\endgroup\$ – Martin Ender Jan 4 '18 at 15:41
  • 3
    \$\begingroup\$ I like sequence challenges that are not decision-problems in general, but for this one I think a decision-problem would be a better fit. I see no relation between the terms such that you print the nth or the first n in a clever manner, so maybe allow taking n as input and checking if it is redivosite? \$\endgroup\$ – Mr. Xcoder Jan 4 '18 at 15:44
  • 1
    \$\begingroup\$ @MartinEnder & Mr.Xcoder That was my initial intention (hence the original title which I've just rollbacked to) and I changed my mind. I guess this should not ruin any WIP solution (for the reasons you say), so I've edited it. \$\endgroup\$ – Arnauld Jan 4 '18 at 15:50
  • 5
    \$\begingroup\$ @Mr.Xcoder Yeah, that's what I meant. I don't mind sequence challenges which actually make sense as a sequence (either because you can compute a(n) directly, or because you can compute a term from previous ones). Thanks, Arnauld, for changing the challenge. :) \$\endgroup\$ – Martin Ender Jan 4 '18 at 16:01

18 Answers 18

9
\$\begingroup\$

Haskell, 91 85 83 80 75 74 bytes

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

Try it online!

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

Edit: -2 bytes thanks to @BMO, -3 bytes thanks to @H.PWiz and -5 -6 bytes thanks to @Ørjan Johansen

\$\endgroup\$
6
\$\begingroup\$

Husk, 14 bytes

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

Try it online!

-3 thanks to H.PWiz.

\$\endgroup\$
  • \$\begingroup\$ 14 bytes with a cleaner function inside Ω \$\endgroup\$ – H.PWiz Jan 4 '18 at 18:51
  • \$\begingroup\$ @H.PWiz just can't understand Γ... \$\endgroup\$ – Erik the Outgolfer Jan 4 '18 at 19:11
  • \$\begingroup\$ Here Γ, given a list [a,b,c...] will apply ~+→Π to a and [b,c...]. ~+→Π adds a+1 to product[b,c...]. a is the smallest divisor, product[b,c...] is N/d \$\endgroup\$ – H.PWiz Jan 4 '18 at 19:14
  • \$\begingroup\$ @H.PWiz And I did think of using prime factors... \$\endgroup\$ – Erik the Outgolfer Jan 4 '18 at 21:44
6
\$\begingroup\$

C (gcc), 94 89 bytes

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;}

Try it online!

Explanation

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
\$\endgroup\$
4
\$\begingroup\$

Jelly, 14 bytes

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

Try it online!

How it works

ÆḌḊ         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.
\$\endgroup\$
4
\$\begingroup\$

Python 2, 97 91 bytes

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

Try it online!

Outputs via exit code.

Ungolfed:

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.

Try it online!

\$\endgroup\$
3
\$\begingroup\$

05AB1E, 17 16 bytes

[Dp#Òć©sP+>]Ö®p*

Try it online!

Explanation

[                  # 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
\$\endgroup\$
2
\$\begingroup\$

Pyth, 20 bytes

<P_QiI.WtPHh+/ZKhPZK

Try it here!

How it works

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.

And the first 4 bytes (<P_Q) just check if the input is not prime.

With help from Emigna, I managed to save 3 bytes.

\$\endgroup\$
  • \$\begingroup\$ Can you use something like head(P) instead of the fiITZ2 part, since the smallest divisor greater than 1 will always be a prime? \$\endgroup\$ – Emigna Jan 4 '18 at 17:00
  • \$\begingroup\$ @Emigna Ninja'd, fixed and thanks! \$\endgroup\$ – Mr. Xcoder Jan 4 '18 at 17:10
2
\$\begingroup\$

Python 3, 149 bytes

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

Try it online!

Using a sieve approach. Should be fast (O(N log log N) = time complexity of the sieve of Eratosthenes) even with large N (but stores O(N) integers in memory)

Note:

  • It can be proven that all intermediate values of n does not exceed N, and for N > 7 p can be in range(2,N) instead of range(2,N+1) for sieving.
  • / doesn't work, // must be used, because of list index.
  • Storing range into another variable doesn't help, unfortunately.

Explanation:

  • -~N == N+1.
  • At first, the array s is initialized with N+1 zeroes (Python is 0-indexing, so the indices are 0..N)
  • After initialization, s[n] is expected to be 0 if n is a prime, and p for p the minimum prime which divides n if n is a composite. s[0] and s[1] values are not important.
  • For each p in range [2 .. N-1]:

    • If s[p] < 1 (that is, s[p] == 0), then p is a prime, and for each q being a multiple of p and s[q] == 0, assign s[q] = p.
  • The last 2 lines are straightforward, except that n//s[n]-~s[n] == (n // s[n]) + s[n] + 1.


Python 3, 118 bytes

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

Try it online!

At the cost of slightly worse performance. (This one runs in O(N log N) time complexity, assume reasonable implementation of Python slices)


The equivalent full program is 117 bytes.

\$\endgroup\$
  • \$\begingroup\$ You can use n//s[n]-~s[n] instead of n//s[n]+s[n]+1 for 149 bytes. \$\endgroup\$ – Mr. Xcoder Jan 4 '18 at 16:12
  • \$\begingroup\$ @Mr.Xcoder Thanks! \$\endgroup\$ – user202729 Jan 4 '18 at 16:13
  • \$\begingroup\$ Also I think or p can be |p \$\endgroup\$ – Mr. Xcoder Jan 4 '18 at 16:14
  • \$\begingroup\$ @Mr.Xcoder No, or p performs logical or, while |p performs bitwise or. That is, a or b is b if a == 0 else a. \$\endgroup\$ – user202729 Jan 4 '18 at 16:23
  • \$\begingroup\$ You can modify the outer for to use slice instead another for. The range is reversed, so lower indexes will overwrite the larger ones, and starting the slice at 2*p you won't replace s[0] or s[p]. \$\endgroup\$ – Rod Jan 4 '18 at 18:37
1
\$\begingroup\$

Haskell, 110 bytes

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]

Try it online!

Not very happy...

\$\endgroup\$
1
\$\begingroup\$

Octave, 92 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog), 50 bytes

{(0=n|⍵)∧⍵>n←{⍬≢k←o/⍨0=⍵|⍨o←2↓⍳⍵:∇1+d+⍵÷d←⌊/k⋄⍵}⍵}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Japt, 25 24 bytes

I fear I may have gone in the wrong direction with this but I've run out of time to try a different approach.

Outputs 0 for false or 1 for true.

j ?V©vU :ßU/(U=k g)+°UNg

Try it

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 291+1(-a) = 292 bytes

Darn Perl for not having a native prime checker.

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;}}}

Ungolfed version,

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;
        }
    }
}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 64 bytes

Straightforward implementation using recursive pattern replacement

(replacing "\[Divides]" with the "∣" symbol saves 7 bytes)

(g=!PrimeQ@#&)@#&&(#//.x_/;g@x:>x/(c=Divisors[x][[2]])+c+1)\[Divides]#&

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Clean, 128 117 114 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

J, 35 bytes

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

Try it online!

The minimum divisor being the first prime factor was stolen from @Dennis's Jelly solution (previously I was using <./@q:).

There should be a better way to do the iteration, but I can't seem to find it. I thought of avoiding doing the primality test (^:(0&p:)) and instead using adverse but it seems like that will be a bit longer since you'll need a _2{ and some changes which might not give a net reduction.

I really feel like there must be a way to avoid having parens around the primality check, too.

Explanation (expanded)

(~: * 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
\$\endgroup\$
0
\$\begingroup\$

APL NARS, 43 chars, 85 bytes

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

(hoping that it converge for all number>6) test:

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  

The idea of using 2 anonymous functions I get to other Apl solution.

 {(⍵≤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
\$\endgroup\$
0
\$\begingroup\$

Pyt, 44 bytes

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

See the code below for an explanation - the only differences are (1) that N is decremented before to account for the incrementation at the beginning of the loop, and (2) it uses NOR instead of OR.

Try it online!



I made this before I re-read the question and noticed that it only wanted a true/false.

Pyt, 52 bytes

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

Prints an infinite list of Redivosite numbers.

Explanation:

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)


Try it online!

\$\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.