Anti-divisors of a number

Question

Given a positive integer n, output all of its anti-divisors in any order.

From OEIS A006272:

Anti-divisors are the numbers that do not divide a number by the largest possible margin. E.g. 20 has anti-divisors 3, 8 and 13. An alternative name for anti-divisor is unbiased non-divisors.

In other words, 1 < m < n is an anti-divisor of n if either

• m is even and n % m == m/2, or
• m is odd and n % m is equal to either (m-1)/2 or (m+1)/2.

Notably, 1 is not an anti-divisor of any number because it does not satisfy the phrase "do not divide a number".

Standard code-golf rules apply. Shortest code in bytes wins.

Test cases

1 -> []
2 -> []
3 -> [2]
4 -> [3]
5 -> [2, 3]
6 -> [4]
7 -> [2, 3, 5]
8 -> [3, 5]
9 -> [2, 6]
10 -> [3, 4, 7]
18 -> [4, 5, 7, 12]
20 -> [3, 8, 13]
234 -> [4, 7, 12, 36, 52, 67, 156]
325 -> [2, 3, 7, 10, 11, 21, 26, 31, 50, 59, 93, 130, 217]

Answer 1

Python 2, 46 bytes

lambda n:[m for m in range(2,n)if-2<n%m*2-m<2]

Try it online!

Answer 2

R, 32 31 bytes

Edit: -1 byte thanks to @Dominic van Essen.

\(n,m=1:n)m[(n%%m-m/2)^2<1][-1]

Attempt This Online!

Pretty much similar to other answers.

The n=1 is problematic: we can't use m=2:n as this would result in m=2:1=c(2,1). So we use m=1:n and then remove the first element (1) with [-1] at the end.

Answer 3

PARI/GP, 30 bytes

-2 bytes thanks to @xnor.

-1 byte thanks to @pajonk and @Dominic van Essen

n->[d|d<-[2..n],(n%d-d/2)^2<1]

Attempt This Online!

Answer 4

Jelly, 8 bytes

%RḤ_RỊTḊ

Try it online!

Feels... messy, but the best I can think of to reuse the range ties: Ḋ%Ḥ_Ịʋ@Ƈ

%R          n mod each [1 .. n]
  Ḥ         times 2
   _R       minus each corresponding [1 .. n]
     Ị      in [-1 .. 1]?
      T     Find truthy indices
       Ḋ    and remove the first (always 1).

Answer 5

Knight, 40 34 bytes

-6 bytes thanks to @Bubbler by looping backwards

;=i=pE P W<1=i-iT&>4^-*2%p i i 2Oi

Try It Online!

Outputs each anti-divisor in a separate line.

I feel like there's just way too much whitespace; there must be a some rearrangement that can avoid some of this whitespace lol

Answer 6

Fig, \$14\log_{256}(96)\approx\$ 11.524 bytes

Fpax'>2A-h%x#x

Try it online!

Fpax'>2A-h%x#x
  ax            - Range [1..input]
 p              - Remove the first item to make this [2..input]
F   '           - Filter by (where the current item is x):
          %x#x  -  Modulo x by the input
         h      -  Multiply that by 2
       A-       -  Get the absolute difference between x and that
     >2         -  Is it less than 2?

Answer 7

Raku, 31 bytes

{grep {1>$_%$^a-$a/2>-1},2..$_}

Try it online!

Anonymous code block that takes a number and returns a list.

Answer 8

05AB1E, 8 bytes

L¦ʒ%·yα!

Try it online or verify all test cases.

Explanation:

L         # Push a list in the range [1, (implicit) input]
 ¦        # Remove the leading 1 to make the range [2,input]
  ʒ       # Filter this list by:
   %      #  Modulo the (implicit) input by the current value
    ·     #  Double it
     yα   #  Get the absolute difference with the current value
       !  #  Factorial (1 remains 1; 0 becomes 1; everything else just increases)
          #  (only 1 is truthy in 05AB1E)
          # (after which the filtered list is output implicitly)

Answer 9

APL (Dyalog Classic), 23 bytes

{1↓⍵{(2>|⍵-2×⍵|⍺)/⍵}⍳⍵}

Try it online!

Usage:

      antidiv←{1↓⍵{(2>|⍵-2×⍵|⍺)/⍵}⍳⍵}
      antidiv 10
3 4 7
      antidiv 325
2 3 7 10 11 21 26 31 50 59 93 130 217

Answer 10

Vyxal, 8 bytes

Ḣ'?$%dεṅ

Try it Online!

-1 byte thanks to lyxal

Answer 11

Factor, 61 bytes

[ dup [1,b] [ [ mod 2 * ] keep - [-1,1]? ] with filter rest ]

Try it online!

One of six variations I tried that all come out to 61 bytes. Went with this one because I've never used [-1,1]? in a golf before and I think it's a neat word.

Answer 12

JavaScript (SpiderMonkey), 39 bytes

n=>{for(i=n;--i;)n%i-i/2|i<2||print(i)}

Try it online!

Answer 13

Regex (ECMAScript 2018 / Python^regex / .NET), 35 31 bytes

(?=((x+)\2(x?$))(?<=^\3?\2\1*))

Try it online! - ECMAScript 2018 / Try it online! - test cases only
Try it online! - Python _{^{import regex}} / Try it online! - test cases only
Try it online! - .NET / Try it online! - test cases only

Takes its input in unary, as a string of x characters whose length represents the number. Outputs its result as the list of matches' \1 captures.

This version takes advantage of variable-length lookbehind that is right-to-left evaluated:

                     # tail = conjectured anti-divisor
(?=
    (                # \1 = tail
        (x+)\2(x?$)  # \2 = floor(tail / 2); \3 = tail % 2; tail = 0;
                     # head = input number
    )
    (?<=             # Variable-length lookbehind; read from bottom to top.
        ^            # Assert head == 0
        \3?          # optionally, head -= \3
        \2           # Assert head ≥ \2; head -= \2
        \1*          # head %= \1; due to backtracking this result may also have
                     # a multiple of \1 added to it, but it will not be able to
                     # match in that case since \2+\3 is guaranteed to be less
                     # than \1.
    )
)

Regex (_{^{ECMAScript 2018 /}} Java _{^{/ Pythonregex / .NET}}), 38 37 bytes

(?=((x+)\2(x?)))(?<=(?=^\1*\2\3?$).*)

Try it online! - ECMAScript 2018 / Try it online! - test cases only
Try it online! - Java / Try it online! - test cases only
Try it online! - Python _{^{import regex}} / Try it online! - test cases only
Try it online! - .NET / Try it online! - test cases only

Java has variable-length lookbehind, with some limits, including that it's not right-to-left evaluated.

                    # tail = conjectured anti-divisor
(?=
    (               # \1 = tail
        (x+)\2(x?)  # \2 = floor(tail / 2); \3 = tail % 2
    )
)
(?<=                # Variable-length lookbehind
    (?=
        ^           # Assert we're at the beginning of the string;
                    # tail = input number
        \1*         # tail %= \1
        \2          # Assert tail ≥ \2; tail -= \2
        \3?         # optionally, tail -= \3
        $           # Assert tail == 0
    )
    .*              # Skip to beginning of string
)

Regex (Perl / PCRE2 _{^{/ Pythonregex}}), 44 43 bytes

(?=((x+)\2(x?)))((?<=(?=^\1*\2\3?$|(?4)).))

Try it online! - Perl / Try it online! - test cases only
Try it online! - PCRE2 / Try it online! - test cases only

Emulates variable-length lookbehind using recursion and fixed-length lookbehind.

Regex (_{^{Perl /}} PCRE _{^{/ Pythonregex}}), 46 45 bytes

(?=((x+)\2(x?)))((?<=(?=z|^\1*\2\3?$|(?4)).))

Try it online! - Perl / Try it online! - test cases only
Try it online! - PCRE1 / Try it online! - test cases only
Try it online! - PCRE2 / Try it online! - test cases only

Works around PCRE1 being picky about recursion it thinks can be endless.

Both Perl/PCRE versions work on the latest version of Python^regex, but not the one on TIO.

Answer 14

Desmos, 40 bytes

l=[1...n][2...]
f(n)=l[-2<2mod(n,l)-l<2]

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 15

Prolog (SWI), 54 53 bytes

Huge thanks to JoKing for helping me out immensely for this answer, from debugging my errors and helping me find solutions to my problems

Also -1 byte thanks to JoKing

N+X:-findall(M,(between(2,N,M),(N mod M*2-M)^2<4),X).

Try it online!

Answer 16

Julia 1.0, 30 28 bytes

Golfing further Ashlin Harris's solution formula

~n=(N=2:n;@.N[-1<n%N-N/2<1])

Try it online!

Answer 17

Julia 1.0, 37 30 bytes

~n=filter(m->-1<n%m-m/2<1,2:n)

Try it online!

-7 bytes thanks to amelies: improve inequality, pass range directly to filter

Answer 18

Java 8, 69 64 bytes

n->{for(int i=1;++i<n;)if((n%i*2-i)/2==0)System.out.println(i);}

-5 bytes thanks to @Deadcode

Outputs the results to STDOUT on separated lines.

Try it online.

Explanation:

n->{                           // Method with integer parameter and no return-type
  for(int i=1;++i<n;)          //  Loop `i` in the range (1,input]:
    if((n%i*2-i)               //   If the input modulo `i`, doubled, minus `i`
       /2                      //   integer-divided by 2
         ==0)                  //   equals 0:
      System.out.println(i);}  //    Print `i` with trailing newline

Answer 19

Haskell, 38 bytes

h n=[m|m<-[2..n-1],abs(mod n m*2-m)<2]

Try it online!

Answer 20

Nibbles, 8 bytes (16 nibbles)

>>|,$~-!=$*%@$~~

  |                 # filter 
   ,$               # the list 1..input
     ~              # by the falsy results of
       !=           # the abxolute difference between
         $          # each element and
          *   ~     # twice (2 is default value '~' for multiplication)
           %@$      # modulo of input by each element
      -        ~    # minus 1 (1 is default value '~' for subtraction)
                    # (note that zero and negative numbers are falsy);
>>                  # finally remove the first element (always 1)

Answer 21

Brachylog, 16 bytes

>.&;.%×₂;.-ȧ<2≤≜

A predicate that acts as a generator. Try it online!

Explanation

Brachylog's clunky arithmetic builtins make it less than ideal for this challenge. Maybe there's a better way to do it.

>.&;.%×₂;.-ȧ<2≤≜
>.                The output is less than the input
  &               And the input
   ;.%            Modulo the output
      ×₂          Times 2
        ;.-       Difference with the output
           ȧ      Absolute value
            <2    Is less than 2
              ≤   Which is less than or equal to
               ≜  A specific number
                  Which is the output

Answer 22

Ruby, 36 bytes

->n{(2..n).select{(n%_1*2-_1)**2<4}}

Attempt This Online!

Answer 23

Go, 119 117 bytes

func(n int)(a[]int){for i:=2;i<n;i++{k:=n%i
if i%2<1&&k==i/2||i%2>0&&(k==(i-1)/2||k==(i+1)/2){a=append(a,i)}}
return}

Attempt This Online!

• -2 bytes by making an anonymous function

Answer 24

MathGolf, 13 bytes

╒╞g{_k\%∞-±2<

Try it online.

Explanation:

╒              # Push a list in the range [1, (implicit) input]
 ╞             # Remove the leading 1 to make the range [2,input]
  g            # Filter this list by,
   {           # using an arbitrary large inner code-block:
               #  (implicitly push the filter index and value)
    _          #  Duplicate the value
     k         #  Push the input-integer
      \        #  Swap so the value is at the top again
       %       #  Modulo the input by the value
        ∞      #  Double it
         -     #  Subtract the two values from one another
          ±    #  Get the absolute value of this
           2<  #  Check that this is smaller than 2 (so either 0 or 1)
               # (after which the entire stack is output implicitly as result)

Answer 25

Charcoal, 16 bytes

ＮθＩΦ…²θ‹↔⁻⊗﹪θιι²

Try it online! Link is to verbose version of code. Explanation:

Ｎθ                  First input as a number
    …               Range from
     ²              Literal integer `2` to
      θ             Input number
   Φ                Filtered where
            θ       Input number
           ﹪        Modulo
             ι      Current value
          ⊗         Doubled
        ↔⁻          Absolute difference with
              ι     Current value
       ‹            Is less than
               ²    Literal integer `2`
  Ｉ                 Vectorised cast to string
                    Implicitly print each value on its own line

Answer 26

C (gcc), ⁵⁸ 52 bytes

m;f(n){for(m=1;++m<n;)(n%m*2-m)/2||printf("%d ",m);}

Try it online!

Saved 6 bytes thanks to the suggestion of porting Kevin's answer by Neil!!!

Port of Kevin Cruijssen's Java answer.

Answer 27

lin, 33 bytes

.#n.n.<1drop".n.+_ %.~2/ -2^1<".#

Try it here!

For testing purposes (use -i flag when running locally):

1 11 .-> 18 20 234 325 ( ;.$$ ).'
.#n.n.<1drop".n.+_ %.~2/ -2^1<".#

Explanation

Prettified code:

.#n .n.< 1drop (.n.+_ %.~ 2/ - 2^ 1< ).#

Assuming input n.

• .n.< 1drop range [n, 2]
• (...).# filter...
  • .n.+_ %.~ 2/ - 2^ 1< equivalent to (n%m - m/2)^2 < 1

Answer 28

Perl 5 -n, 35 bytes

//;map{abs($'%$_*2-$_)<2&&say}2..$_

Try it online!

Uses a take on xnor's formula in his python answer.

Answer 29

x86 64-bit machine code, 26 bytes

89 F1 51 8D 44 71 01 99 01 C9 F7 F1 58 83 FA 02 77 01 AB 91 E2 EC FF 4F FC C3

Try it online!

Takes \$n\$ in ESI and writes the anti-divisors as consecutive 32-bit integers, terminated with a 0, to an address given in RDI.

In assembly:

f:  mov ecx, esi
r:  push rcx
    lea eax, [2*rsi+rcx+1]
    cdq
    add ecx, ecx
    div ecx
    pop rax
    cmp edx, 2
    ja s
    stosd
s:  xchg ecx, eax
    loop r
    dec DWORD PTR [rdi-4]
    ret

Answer 30

Japt -f, 12 bytes

ÊÉ©AìøUaN%UÑ

Try it

Without Flags, 13 bytes

õ ÅkÈaU%XÑ ÊÉ

Try it

ÊÉ©AìøUaN%UÑ     :Implicit filter of each U in range [0,input)
Ê                :Factorial
 É               :Subtract 1
  ©              :Logical AND with
   A             :10
    ì            :To digit array
     ø           :Contains?
      Ua         :  Absolute difference of U and
        N        :    Array of all inputs (singleton, in this case)
         %U      :    Mod U
           Ñ     :    Multiplied by 2

õ ÅkÈaU%XÑ ÊÉ     :Implicit input of integer U
õ                 :Range [1,U]
  Å               :Remove first element
   k              :Remove elements that return true
    È             :When passed through the following function as X
     a            :  Absolute difference with
      U%XÑ        :    U mod X times 2
           Ê      :  Factorial
            É     :  Subtract 1