24
\$\begingroup\$

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 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]
\$\endgroup\$

33 Answers 33

9
\$\begingroup\$

Python 2, 46 bytes

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

Try it online!

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ 31 bytes \$\endgroup\$ Aug 10, 2022 at 16:01
  • \$\begingroup\$ @DominicvanEssen that's neat, thanks! \$\endgroup\$
    – pajonk
    Aug 10, 2022 at 17:45
  • 1
    \$\begingroup\$ 30 bytes (I think)... \$\endgroup\$ Aug 11, 2022 at 13:38
6
\$\begingroup\$

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!

\$\endgroup\$
2
5
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ 35 bytes: ;=i=pE P W<1=i-i 1&>4^-*2%p i i 2Oi \$\endgroup\$
    – Bubbler
    Aug 10, 2022 at 6:44
  • \$\begingroup\$ @Bubbler Yo that's like actually super smart, going backwards \$\endgroup\$
    – Aiden Chow
    Aug 10, 2022 at 6:49
  • \$\begingroup\$ i actually save another byte by doing -iT instead of -i 1 \$\endgroup\$
    – Aiden Chow
    Aug 10, 2022 at 6:53
  • \$\begingroup\$ Nice Trick there! \$\endgroup\$
    – Bubbler
    Aug 10, 2022 at 8:05
4
\$\begingroup\$

Raku, 31 bytes

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

Try it online!

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

\$\endgroup\$
4
\$\begingroup\$

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

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Aug 10, 2022 at 14:51
  • \$\begingroup\$ @NoHaxJustRadvylf Thanks! \$\endgroup\$
    – atpx8
    Aug 10, 2022 at 14:53
3
\$\begingroup\$

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.

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

JavaScript (SpiderMonkey), 39 bytes

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

Try it online!

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

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

Regex (ECMAScript 2018 / Pythonregex / .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 Pythonregex, but not the one on TIO.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ The atomicity seems unnecessary, or am I missing something: Try it online! (would be shorter in Retina 1)? \$\endgroup\$
    – Neil
    Aug 10, 2022 at 11:06
  • 1
    \$\begingroup\$ @Neil You're right, the atomicity is unnecessary, thanks. That's what I get for staying up late coding. Nice Retina code; that must be using overlapping matches, otherwise the lookahead is needed. (I avoided invoking overlapping matches because doing so would stray away from pure regex.) I'm guessing that Retina version is probably shorter than one that puts the list in a capture group's stack. \$\endgroup\$
    – Deadcode
    Aug 10, 2022 at 14:41
  • \$\begingroup\$ Yes, the & option to Match mode is the only support Retina 0.8.2 has for overlapping matches, similar to Retina 1's v option. \$\endgroup\$
    – Neil
    Aug 10, 2022 at 14:42
3
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Ah, nice, that's much cleaner than what I came up with (being a newbie at Desmos). \$\endgroup\$
    – Deadcode
    Aug 10, 2022 at 17:53
3
+200
\$\begingroup\$

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!

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

Vyxal, 8 bytes

Ḣ'?$%dεṅ

Try it Online!

-1 byte thanks to lyxal

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

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?
\$\endgroup\$
6
  • \$\begingroup\$ p}TM'>2xmQ-axh%a shaves off a byte. \$\endgroup\$
    – naffetS
    Sep 28, 2022 at 3:04
  • 1
    \$\begingroup\$ Fpax'>2A-h%x#x is 11.524 bytes (14) \$\endgroup\$
    – naffetS
    Sep 28, 2022 at 3:10
  • \$\begingroup\$ I could not manage to get A to work. From my understanding, given a single integer it's absolute value right? Also, if you want to explain how your second improvement works, that would be cool. \$\endgroup\$
    – south
    Sep 28, 2022 at 4:32
  • 1
    \$\begingroup\$ @south yes A is abs, but it also does not vectorise \$\endgroup\$
    – Seggan
    Sep 28, 2022 at 12:17
  • \$\begingroup\$ @south The second improvement is similar to your current one, but using F (filter) to instead filter the range [1..input] instead of using truthy indices. \$\endgroup\$
    – naffetS
    Sep 28, 2022 at 18:13
2
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ -5 bytes \$\endgroup\$
    – Deadcode
    Aug 10, 2022 at 7:15
  • 1
    \$\begingroup\$ @Deadcode Ah, of course! Seems so obvious now that I see it. Thanks. :) \$\endgroup\$ Aug 10, 2022 at 7:17
2
\$\begingroup\$

Haskell, 38 bytes

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

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ You can save 1 by using square instead of abs Try it online! \$\endgroup\$
    – AZTECCO
    Aug 11, 2022 at 13:58
2
\$\begingroup\$

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)

enter image description here

\$\endgroup\$
2
\$\begingroup\$

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

Ruby, 36 bytes

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

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 32 bytes ~n=filter(m->abs(n%m-m/2)<1,2:n) \$\endgroup\$
    – amelies
    Oct 27, 2022 at 21:12
1
\$\begingroup\$

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

Charcoal, 16 bytes

NθIΦ…²θ‹↔⁻⊗﹪θιι²

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

Nθ                  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`
  I                 Vectorised cast to string
                    Implicitly print each value on its own line
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 58 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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Porting @Deadcode's Java golf seems to save you 6 bytes... \$\endgroup\$
    – Neil
    Aug 10, 2022 at 14:38
  • \$\begingroup\$ @Neil Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    Aug 10, 2022 at 16:02
1
\$\begingroup\$

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

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.

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

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

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

Go, 119 bytes

func f(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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.