Różnice par dzielników MaxMin (DMDP)

18

Porozmawiajmy o dzielnikach ...

Pomijając na chwilę idealne kwadraty, wszystkie dodatnie liczby całkowite można wyrazić jako iloczyn 2 ich dzielników. Szybki przykład dla 126: Oto wszystkie dzielniki126
wprowadź opis zdjęcia tutaj

Jak widać, wszystkie dzielniki można sparować. Oto, co nazwiemy parami dzielników :
[1, 126], [2, 63], [3, 42], [6, 21], [7, 18], [9, 14]

Do tego wyzwania potrzebujemy tylko ostatniej pary z tej listy (która jest środkową parą obrazka):
[9,14]Nazwiemy tę parę parą dzielnika MaxMin . Różnica maxmin dzielnik Pair (DMDP) jest różnicą pomiędzy dwoma elementami pary, która jest jeszcze jeden przykład dla . Dzielnikami są:
[9,14]=5
544

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

i DMDP (544) = 15, ponieważ32-17=15

Co z idealnymi kwadratami ? Wszystkie idealne kwadraty mają DMDP = 0
Weźmy na przykład 64dzielniki

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

Jak widać w tym przypadku, para dzielników MaxMin jest [8,8]już DMDP=0
prawie gotowa.

Wyzwanie

Biorąc pod uwagę liczbę całkowitą n>0, wypisz ile liczb całkowitych mniejszych lub równych 10000 , DMDP mniej niż n

Przypadki testowe

wejście -> wyjście

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

To jest Krótka odpowiedź w bajtach wygrywa .


źródło
Czy nie byłoby sensowniej mieć 10000drugą zmienną wejściową?
Jonathan Allan
1
Tak, myślałem o tym, ale nie dodałoby to niczego do wyzwania. W ten sposób myślę, że wszystkim łatwiej jest zrozumieć wyzwanie.
1
Powiązane
Peter Taylor

Odpowiedzi:

5

JavaScript (ES7), 60 bajtów

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

Prawdopodobnie przekracza limit rekurencji, więc możesz wybrać wersję iteracyjną dla 70 bajtów:

n=>[...Array(1e4)].map(g=(j=++i**.5|0)=>i%j?g(j-1):k+=i/j-j<n,i=k=0)|k
Neil
źródło
4

Galaretka , 13 bajtów

1 bajt dzięki Jonathan Allan.

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

Wypróbuj online!

Leaky Nun
źródło
ÆDạ"Ṛ$Ṃoszczędza ci bajt ÆDạ:@¥⁸Ṃ(miałem ạ"ṚṂ... ȷ4RÆDÇ€<⁸Sza 15 - zbyt podobny - EDYCJA: hmm, czy to było, nie było :zaangażowane ... co myślisz?)
Jonathan Allan
@JonathanAllan Myślę, że powinieneś opublikować ten 13-bajter
Leaky Nun
Och wow. nie, idź po to, zapisałem ci jeden bajt, który oszczędza kolejne 2!
Jonathan Allan
Czy możesz dodać wyjaśnienie?
Kevin Cruijssen
4

Java 8, 151 111 110 101 bajtów

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 bajtów dzięki @Nevay .

Wyjaśnienie:

Wypróbuj tutaj.

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
Kevin Cruijssen
źródło
1
Możesz użyć, for(i=1,i+=Math.sqrt(x);--i>0;)if(...aby zapisać 1 bajt.
Nevay
Nie mam czasu na samodzielne wypróbowanie, ale czy krótsza byłaby pętla wewnętrzna zaczynająca się od x i posiadająca dodatkową zmienną dla aktualnego minimum?
JollyJoker
1
101 bajtów: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;}
Nevay
@Nevay Jeszcze raz dziękuję, naprawdę muszę pamiętać x>=i*ijako alternatywę dla używania Math.sqrt, ponieważ po raz drugi grałeś w golfa w moim kodzie.
Kevin Cruijssen
2

R , 73 77 bajtów

Dzięki @Guiseppe za 4 bajty

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

Wypróbuj online!

Straciłem funkcję wektoryzacji, aby obliczyć DMDP, i używa teraz sapply nad funkcją. Prawdy dla przedmiotów, które są mniejsze niż dane wejściowe, są sumowane dla wyniku.

MickyT
źródło
Ach, nie zauważyłem, że DMDP jest minimalną różnicą z tej listy czynników! Bardzo dobrze. Myślę, że sum(sapply(1:1e4,function(x)min(abs((w=which(x%%1:x<1))-rev(w))))<scan())jest nieco krótszy
Giuseppe
2

Mathematica, 64 bajty

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

Wypróbuj na Wolfram Sandbox

Stosowanie

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}

Wyjaśnienie

Divisors~Array~1*^4

Wygeneruj listy dzielników, od 1do 10000. (listy dzielników są sortowane automatycznie)

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

Policz wystąpienia elementów a, takie jak ...

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

(input) + (left one of the middle element(s)) > (right one of the middle element(s)) Jeśli jest tylko jeden środkowy element, left = right.

JungHwan Min
źródło
2

05AB1E , 19 18 17 16 15 12 bajtów

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

Wypróbuj online!

Wyjaśnienie

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
Emigna
źródło
1

MATL , 20 bajtów

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

Przekroczono limit czasu w TIO. Oto przykład uruchomienia z kompilatorem offline:

>> matl 1e4:"@Z\2Y"dJ2/)G<vs
> 13
1201
Luis Mendo
źródło
1

R , 91 bajtów

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

Przy obliczaniu DMDP stosuje inne (gorsze) podejście niż rozwiązanie MickyT, stosując indeksowanie tablic i diffobliczanie go. Niestety.

Wypróbuj online!

Giuseppe
źródło
1

Mathematica, 119 115 bajtów

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

W końcu udało mi się to uruchomić i próbowałem przez ostatnie pół godziny. ._.

Przykładowy przebieg

brak opisu dla ciebie!

całkowicie ludzki
źródło
CasesJest 4bajtów krócej: Tr[1^Cases[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+(1+Length@Divisors@#)/2]]&/@Range@10000),n_/;n<#]]&. Zobacz tę wskazówkę .
ngenisis
1
@ngenisis Countjest nawet krótszy niż Cases. Count[Last@#-First@#&/@(Take[Divisors@#,Round[{-.1,.1}+‌​(1+Length@Divisors@#‌​)/2]]&/@Range@10000)‌​,n_/;n<#]&
JungHwan Min
Także 10^4lub 1*^4jest krótszy niż 10000i /@Range@jest równoważny ~Array~.
JungHwan Min
1

Mathematica, 78 bajtów

(s=#;Tr[1^Select[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],#<s&]])&
J42161217
źródło
CasesJest 4bajtów krócej: Tr[1^Cases[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^4}],s_/;s<#]]&. Zobacz tę wskazówkę .
ngenisis
1
@ngenisis Countjest jeszcze krótszy:Count[Table[#2-#&@@Quantile[Divisors@i,{.5,.51}],{i,10^‌​4}],s_/;s<#]&
JungHwan Min
1

Łuska , 19 bajtów

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

Brak linku TIO, ponieważ upłynął limit czasu. Ta wersja używa 100 zamiast 10000 i kończy się w ciągu kilku sekund.

Wyjaśnienie

Husk nie ma jeszcze wbudowanych dzielników ani wsparcia notacji naukowej.

#ȯ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?
Zgarb
źródło
1

Japt , 25 19 17 bajtów

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

Sprawdź to


Wyjaśnienie

Domniemane wprowadzenie liczby całkowitej U.

L²õ

Wygeneruj tablicę liczb całkowitych ( õ) od 1 do 100 ( L) podniesionych do kwadratu.

Èâ          Ã

Przekaż każdą przez funkcję (gdzie Xjest bieżącym elementem), która generuje tablicę dzielników ( â) z X.

®    Ã

Odwzoruj na tej tablicy dzielników, gdzie Zjest bieżący element.

aX/Z

Uzyskaj różnicę bezwzględną ( a) Zi Xpodzielone przez Z.

d<U

Czy któryś z elementów ( d) w wynikowej tablicy jest mniejszy niż U?

è

Policz prawdziwe elementy i w sposób dorozumiany wyprowadź wynik.

Kudłaty
źródło
1

TI-BASIC, 46 bajtów

Zauważ, że TI-BASIC jest językiem tokenizowanym. Ponadto E w wierszu 2 jest małą dużą literą E, znalezioną po naciśnięciu 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

Wynik będzie w D, a Ans natychmiast po wykonaniu programu. Jeśli ma być wyświetlony, Answystarczy dodać jeszcze dwa bajty (znak nowej linii i ).

Josiah Winslow
źródło
0

Python 2 , 134 bajty

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)]))

Wypróbuj online!

Eugh ... trzeba zrobić znacznie lepiej.

całkowicie ludzki
źródło
125 bajtów (-9 bajtów) przy obecnym podejściu, ale zastępując len(filter(lambda n:n<i,...))jesum(n<i for n in ....)
Mr. Xcoder
114 bajtów na podstawie komentarza Mr.Xcodera.
ovs
113 bajtów na podstawie komentarza ovs.
Pan Xcoder
0

Python 2 , 83 bajty

Trochę wolniej, zużywa 5 sekund na przypadek testowy

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))

Wypróbuj online!

Halvard Hummel
źródło
0

PHP, 94 + 1 bajtów

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

Uruchom jako potok z -nRlub spróbuj online .

Tytus
źródło
0

VB.NET (.NET 4.5) 116 115 bajtów

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

Wyjaśnienie:

Funkcja, która bierze n jako parametr i zwraca wynik.

Zaczyna się od pierwiastka kwadratowego i szuka najbliższej liczby całkowitej, która równomiernie dzieli (będzie mniejsza z MaxMin Divisor Pair). Następnie pobiera większą z pary ( i/s), znajduje różnicę i porównuje dane wejściowe.


Zastosowane strategie golfowe:

  • Dim jest drogi, więc im mniej zmiennych deklaruję, tym lepiej.
  • Zaczynam szukać od pierwiastka kwadratowego, ale chcę tylko patrzeć na liczby całkowite. Deklarującs jako integralny typ, rzuca mnie na podłogę.
  • VB wykorzystuje ^jako wykładnik. Więc chociaż 10000ma 5 znaków, 10^4ma tylko 4.
  • VB tworzy zmienną automatyczną o tej samej nazwie i typie co definicja funkcji (w moim przypadku A). Na końcu funkcji, jeśli nie return, wartość zmiennej funkcji zostanie zwrócona. Zapisuję więc znaki, nie deklarując osobnej zmiennej i nie używając instrukcji return.
  • VB ma bardzo wybaczające pisanie / casting. izakłada się, Integerponieważ przypisałem literałowi całkowitemu. Azakłada się, Objectale jak tylko dodam liczbę całkowitą, zachowuje się jak Integer.
  • Zamiast ifsprawdzać, czy różnica jest zadowalająca, dodaj ją bezpośrednio do wyniku, przesyłając wartość logiczną na liczbę całkowitą. Jednak VB używa -1doTrue , więc odejmij, aby uzyskać poprawny znak.
  • Technicznie rzecz biorąc, chcemy Mod, aby nie być 0. Biorąc moduł liczby ujemnej w VB.NET da wynik ujemny. Ale wszystko jest pozytywne, więc mogę zaoszczędzić bajt, zamieniając się <>w >.
  • Największa liczba do sprawdzenia to 10000. Pierwiastek kwadratowy z tego to 100. Potrzebuję tylko Bytetego, aby zapisać, oszczędzając bajty w deklaracji, używając krótszego nazwanego typu.

Wypróbuj online!

Brian J.
źródło