18
\$\begingroup\$

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
enter image description here

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 .Shortest answer in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't it make more sense to have the 10000 as a second, variable, input? \$\endgroup\$ – Jonathan Allan Aug 29 '17 at 23:35
  • 1
    \$\begingroup\$ Yes, I thought about that but it would not add anything to the challenge. In this way I think it is easier for everybody to understand the challenge. \$\endgroup\$ – user73398 Aug 29 '17 at 23:39
  • 1
    \$\begingroup\$ Related \$\endgroup\$ – Peter Taylor Aug 30 '17 at 7:18

19 Answers 19

5
\$\begingroup\$

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

Jelly, 13 bytes

1 byte thanks to Jonathan Allan.

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ ÆDạ"Ṛ$Ṃ saves you a byte over ÆDạ:@¥⁸Ṃ (I had ạ"ṚṂ...ȷ4RÆDÇ€<⁸S for 15 - too similar - EDIT: hmm or was it, no : involved... what do you think?) \$\endgroup\$ – Jonathan Allan Aug 30 '17 at 0:22
  • \$\begingroup\$ @JonathanAllan I think you should post this 13-byter \$\endgroup\$ – Leaky Nun Aug 30 '17 at 0:25
  • \$\begingroup\$ Oh wow. nah you go for it, I saved you one byte that saves another 2! \$\endgroup\$ – Jonathan Allan Aug 30 '17 at 0:27
  • \$\begingroup\$ Could you add an explanation? \$\endgroup\$ – Kevin Cruijssen Aug 31 '17 at 12:05
4
\$\begingroup\$

Java 8, 151 111 110 101 bytes

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

-10 bytes thanks to @Nevay.

Explanation:

Try it here.

n->{               // Method with integer as parameter and return-type
  int r=0,         //  Result-integer
      x=10000,     //  Index-integer starting at 10,000
      i;           //  Another index-integer for the inner loop
  for(;x-->0;      //  Loop (1) from 10,000 down to 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,       //   Set `i` to `x`
        i-->1;)    //   Inner loop (2) from `i` downwards to 1
      if(x>=i*i    //    If the current square-root of `x` is smaller than or equal to `i`,
         &x%i<1){  //    and if the current `x` is divisible by `i`:
        i=x/i-i;   //     Calculate the MaxMin-Division difference
        break;}    //     And leave the inner loop (2)
                   //   End of inner loop (2) (implicit / single-line body)
                   //  End of loop (1) (implicit / single-line body)
  return r;        //  Return the result
}                  // End of method
\$\endgroup\$
  • 1
    \$\begingroup\$ You can use for(i=1,i+=Math.sqrt(x);--i>0;)if(... to save 1 byte. \$\endgroup\$ – Nevay Aug 30 '17 at 12:49
  • \$\begingroup\$ Don't have time to try it myself, but would it be shorter to have the inner loop start from x and have an extra variable for the current minimum? \$\endgroup\$ – JollyJoker Aug 30 '17 at 13:00
  • 1
    \$\begingroup\$ 101 bytes: n->{int r=0,x=10000,i;for(;x-->0;r-=i-n>>-1)for(i=x;i-->1;)if(x>=i*i&x%i<1){i=x/i-i;break;}return r;} \$\endgroup\$ – Nevay Aug 31 '17 at 10:08
  • \$\begingroup\$ @Nevay Thanks again, really need to remember x>=i*i as alternative for using Math.sqrt, since this is the second time you've golfed that in my code. \$\endgroup\$ – Kevin Cruijssen Aug 31 '17 at 12:04
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Ah, I didn't notice the DMDP is the min diff of that factor list! Very nice. I think sum(sapply(1:1e4,function(x)min(abs((w=which(x%%1:x<1))-rev(w))))<scan()) is a bit shorter \$\endgroup\$ – Giuseppe Aug 29 '17 at 23:54
2
\$\begingroup\$

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.

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

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

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

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!

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

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

no description for you!

\$\endgroup\$
  • \$\begingroup\$ Cases is 4 bytes shorter: Tr[1^Cases[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),n_/;n<#]]&. See this tip. \$\endgroup\$ – ngenisis Aug 30 '17 at 2:23
  • 1
    \$\begingroup\$ @ngenisis actually Count is even shorter than Cases. Count[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+‌​(1+Length@Divisors@#‌​)/2]]&/@Range@10000)‌​,n_/;n<#]& \$\endgroup\$ – JungHwan Min Aug 30 '17 at 3:56
  • \$\begingroup\$ Also, 10^4 or 1*^4 is shorter than 10000, and /@Range@ is equaivalent to ~Array~. \$\endgroup\$ – JungHwan Min Aug 30 '17 at 3:58
1
\$\begingroup\$

Mathematica, 78 bytes

(s=#;Tr[1^Select[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],#<s&]])&
\$\endgroup\$
  • \$\begingroup\$ Cases is 4 bytes shorter: Tr[1^Cases[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],s_/;s<#]]&. See this tip. \$\endgroup\$ – ngenisis Aug 30 '17 at 2:21
  • 1
    \$\begingroup\$ @ngenisis Count is even shorter: Count[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^‌​4}],s_/;s<#]& \$\endgroup\$ – JungHwan Min Aug 30 '17 at 3:57
1
\$\begingroup\$

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

Japt, 25 19 17 bytes

L²õÈâ ®aX/ZÃd<UÃè

Test it


Explanation

Implicit input of integer U.

L²õ

Generate an array of integers (õ) from 1 to 100 (L) squared.

Èâ          Ã

Pass each through a function (where X is the current element) that generates an array of the divisors (â) of X.

®    Ã

Map over that array of divisors, where Z is the current element.

aX/Z

Get the absolute difference (a) of Z and X divided by Z.

d<U

Are any of the elements (d) in the resulting array less than U?

è

Count the truthy elements and implicitly output the result.

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

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.

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

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.

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

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.

\$\endgroup\$
  • \$\begingroup\$ 125 bytes (-9 bytes) using your current approach, but replacing len(filter(lambda n:n<i,...)) with sum(n<i for n in ....) \$\endgroup\$ – Mr. Xcoder Aug 30 '17 at 6:39
  • \$\begingroup\$ 114 bytes based on Mr.Xcoder''s comment. \$\endgroup\$ – ovs Aug 30 '17 at 6:50
  • \$\begingroup\$ 113 bytes based on ovs' comment. \$\endgroup\$ – Mr. Xcoder Aug 30 '17 at 6:52
0
\$\begingroup\$

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!

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

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.

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

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!

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

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy