Differences of MaxMin Divisor Pairs (DMDP)

Question

Let's talk about divisors...

Leaving out perfect squares (for a moment), all positive integers can be expressed as the product of 2 of their divisors. Quick example for 126: Here are all the divisors of 126

As you can see all the divisors can be paired. Here are what we will call the Divisor Pairs:
[1, 126], [2, 63], [3, 42], [6, 21], [7, 18], [9, 14]

For this challenge we will need only the last pair of this list (which is the center pair of the picture):
[9,14].We will call this pair the MaxMin Divisor Pair.
The Difference of MaxMin Divisor Pair (DMDP) is the difference of the two elements of the pair which is [9,14]=5
One more example for 544. The divisors are:

[1, 2, 4, 8, 16, 17, 32, 34, 68, 136, 272, 544]

and DMDP(544)=15 because 32-17=15

What about the perfect squares? All perfect squares have DMDP=0
Let's take for example 64 with divisors

{1, 2, 4, 8, 16, 32, 64}

As you can see in this case the MaxMin Divisor Pair is [8,8] which has DMDP=0
we are almost done..

The Challenge

Given an integer n>0, output how many integers less than or equal to 10000, have DMDP less than n

Test Cases

input -> output

1->100 (those are all the perfect squares)
5->492  
13->1201
369->6175  
777->7264  
2000->8478  
5000->9440  
9000->9888  
10000->10000   
20000->10000
  

This is code-golf.Shortest answer in bytes wins.

Answer 1

JavaScript (ES7), 60 bytes

f=(n,i=1e4,j=i**.5|0)=>i?i%j?f(n,i,j-1):(i/j-j<n)+f(n,i-1):0

Probably exceeds your recursion limit, so you might prefer the iterative version for 70 bytes:

n=>[...Array(1e4)].map(g=(j=++i**.5|0)=>i%j?g(j-1):k+=i/j-j<n,i=k=0)|k

Answer 2

Java 8, 151 111 110 101 98 bytes

n->{int r=0,x=10000,i;for(;x-->0;r-=i-n>>-1)for(i=x;i-->1&&(x<i*i|x%i>0||(i=x/i-i)>i););return r;}

-10 bytes thanks to @Nevay.
-3 bytes thanks to @ceilingcat.

Explanation:

Try it here.

n->{                  // Method with integer as parameter and return-type
  int r=0,            //  Result-integer, starting at 0
      x=10000,        //  Index-integer `x` for the outer loop, starting at 10,000
      i;              //  Index-integer `i` for the inner loop, uninitialized
  for(;x-->0;         //  Loop `x` in the range (10000, 0]:
      r-=i-n>>-1)     //   If the MaxMin-Divisor Pair's difference is lower than the input,
                      //    add 1 to the result (after every iteration)
    for(i=x;i-->1     //   Inner loop `i` in the range (`x`, 1]:
        &&(x<i*i      //    If the current square of `i` is smaller than or equals to `x`,
           |x%i>0     //    and the current `x` is divisible by `i`:
           ||(i=x/i-i)//     Calculate the MaxMin-Division difference
             >i););   //     And stop the inner loop
  return r;}          //  After the loops, return the result

Answer 3

Jelly, 13 bytes

1 byte thanks to Jonathan Allan.

ȷ4RÆDạU$Ṃ€<⁸S

Try it online!

Answer 4

R, 73 77 bytes

Thanks to @Guiseppe for the 4 bytes

sum(sapply(1:1e4,function(x)min(abs((w=which(x%%1:x<1))-rev(w))))<scan())

Try it online!

Have lost the vectorize function to calculate the DMDP and is now using a sapply over the function. The truthies for items which are less than the input are summed for the result.

Answer 5

Mathematica, 64 bytes

Count[Divisors~Array~1*^4,a_/;#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]&

Try it on Wolfram Sandbox

Usage

f = Count[Divisors~Array~1*^4,a_/;#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]&

 

f[1]

100

f /@ {1, 5, 13, 369, 777, 2000, 5000, 9000, 10000, 20000}

{100, 492, 1201, 6175, 7264, 8478, 9440, 9888, 10000, 10000}

Explanation

Divisors~Array~1*^4

Generate the lists of divisors, from 1 to 10000. (the lists of divisors are sorted automatically)

Count[ ..., a_/; ... ]

Count the occurrences of elements a, such that...

#+a[[i=⌈Tr[1^a]/2⌉]]>a[[-i]]]

(input) + (left one of the middle element(s)) > (right one of the middle element(s)) If there is only one middle element, left = right.

Answer 6

05AB1E, 19 18 17 16 15 12 bytes

4°ƒNÑÂα{нI‹O

Try it online!

Explanation

4°ƒ            # for N in [0 ... 10**4] do:
   NÑ          # push divisors of N 
     Â         # bifurcate
      α        # element-wise absolute difference
       {       # sort
        н      # pop the head (smallest difference)
         I‹    # is it smaller than the input?
           O   # sum the stack

Answer 7

MATL, 20 bytes

1e4:"@Z\2Y"dJ2/)G<vs

The code times out in TIO. Here's an example run with the offline compiler:

>> matl 1e4:"@Z\2Y"dJ2/)G<vs
> 13
1201

Answer 8

R, 91 bytes

function(n)sum(sapply(1:1e4,function(x,d=(1:x)[x%%1:x<1])diff(d[median(seq(d))+.5*0:1]))<n)

Takes a different (worse) approach to computing the DMDP than MickyT's solution by using array indexing and diff to compute it. Alas.

Try it online!

Answer 9

Mathematica, 119 115 bytes

(n=#;Tr[1^Select[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),#<n&]])&

I finally got this thing working and I've been trying for the past half an hour. ._.

Example run

Answer 10

Mathematica, 78 bytes

(s=#;Tr[1^Select[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],#<s&]])&

Answer 11

Husk, 19 bytes

#ȯV<⁰Sz≠↔§f`¦ḣḣ□100

No TIO link, since it times out. This version uses 100 in place of 10000 and finishes in a couple of seconds.

Explanation

Husk has no divisors built-in or support for scientific notation yet.

#ȯV<⁰Sz≠↔§f`¦ḣḣ□100  Input is n (accessed with ⁰).
               □100  Square of 100: 10000
              ḣ      Inclusive range from 1.
#                    Count number of elements for which
 ȯ                   this composition of 3 functions gives truthy result:
                       Argument k, say k = 12.
         §f`¦ḣ         Divisors of k:
             ḣ           Range: [1,2,3,..,12]
         §f              Filter by
           `¦            divides k: [1,2,3,4,6,12]
     Sz≠↔              Absolute differences of divisor pairs:
        ↔                Reverse: [12,6,4,3,2,1]
     Sz                  Zip with divisor list
       ≠                 using absolute difference: [11,4,1,1,4,11]
  V<⁰                  Is any of these less than n?

Answer 12

Ruby, 62 bytes

->n{(1..1e4).count{|x|(1..x).any?{|i|1>x%i&&x/i<=i&&i-x/i<n}}}

Try it online.

Answer 13

TI-BASIC, 46 bytes

Note that TI-BASIC is a tokenized language. Also, the E in line 2 is a small capital E, found by pressing 2ND+, .

Input A
DelVar DFor(B,1,E4
For(C,1,√(B
If not(fPart(B/C
B/C-C<A
End
D+Ans→D
End

Result will be in D, and Ans immediately after program execution. If it is to be displayed, adding two more bytes (newline and Ans) would suffice.

Answer 14

Japt -x, 25 19 17 15 bytes

L²õÈâ ËaX/DÃd<U

Try it

L²õÈâ ËaX/DÃd<U     :Implicit input of integer U
L                   :100
 ²                  :Squared
  õ                 :Range [1,L²]
   È                :Map each X
    â               :  Divisors
      Ë             :  Map each D
       aX/D         :    Absolute difference with X/D
           Ã        :  End inner map
            d<U     :  Any less than U?
                    :Implicit output of sum of resulting array

Answer 15

Python 2, 134 bytes

lambda i:len(filter(lambda n:n<i,[reduce(lambda x,y:y-x,[[x,n/x]for x in range(1,int(n**.5+1))if n%x<1][-1])for n in range(1,10001)]))

Try it online!

Eugh... need to do much better.

Answer 16

Python 2, 83 bytes

A bit on the slow side, uses 5 seconds per test case

lambda x:sum(x>min(abs(y/t-t)for t in range(1,y+1)if y%t<1)for y in range(1,10001))

Try it online!

Answer 17

PHP, 94+1 bytes

for(;$n++<1e4;$c+=$d<$argn)if(($i=$n**.5)>~~$i){while($n%++$i);for($d=1;$n%--$i;)$d++;}echo$c;

Run as pipe with -nR or try it online.

Answer 18

VB.NET (.NET 4.5) 116 115 bytes

Function A(n)
For i=1To 10^4
Dim s As Byte=Math.Sqrt(i)
While i Mod s>0
s-=1
End While
A-=i/s-s<n
Next
End Function

---

Explanation:

A function that takes n as a parameter, and returns the result.

Starts at the square root, and looks for the nearest integer that evenly divides (will be the smaller of the MaxMin Divisor Pair). Then gets the larger of the pair (i/s), finds the difference, and compares against the input.

---

Golfing strategies used:

• Dim is expensive, so the fewer variables I declare the better.
• I start searching at the square root, but only want to look at integers. By declaring s as an integral type, it casts to the floor for me.
• VB uses ^ as exponent. So while 10000 is 5 characters, 10^4 is only 4.
• VB creates an automatic variable with the same name and type as the function definition (in my case A). At the end of the function, if there is no return, the value of the function variable will be returned instead. So I save characters by not declaring a separate variable and not using a return statement.
• VB has very forgiving typing/casting. i is assumed Integer because I assigned a integer literal. A is assumed Object but as soon as I add an integer, it behaves like an Integer.
• Rather than if checking the that the difference is satisfactory, add it directly to the result by casting the boolean to an integer. However, VB uses -1 for True, so subtract to get the correct sign.
• Technically, we want Mod to not be 0. Taking the modulus of a negative number in VB.NET will give a negative result. But, everything is positive so I can save a byte by turning <> into >.
• The largest number to check is 10000. The square root of that is 100. So I only need a Byte to store that, saving bytes in the declaration by using a shorter named type.

Try it online!

Answer 19

C# (.NET Core), 104 bytes

x=>{int o=0,i=1;for(;i<=10000;i++)for(int j=1;j<=i;j++)if(i%j<1&Math.Abs(j-i/j)<x){o++;break;}return o;}

Try it online!

Answer 20

Wolfram Language (Mathematica), 52 bytes

Boole@Array[AtomQ@√(4a+#^2)&,#,0,Or]~Sum~{a,1*^4}&

Try it online!

Slow.