Największa liczba w zakresie po odjęciu sumy kwadratów jej głównych czynników

17

Formuła

Weźmy na przykład liczbę 300

  • Czynniki pierwsze 300 to [2, 3, 5](unikalne liczby, które są współczynnikami 300 i liczba pierwsza)
  • Kwadrat każdej z tych liczb da ci [4, 9, 25]
  • Podsumowanie tej listy da ci 4 + 9 + 25 = 38
  • Na koniec odejmij tę sumę (38) od oryginalnego numeru 300-38 = 262(to wynik)

Wejście

Wprowadzona liczba będzie dodatnią liczbą całkowitą większą niż 2. Musisz sprawdzić wszystkie liczby od 2 do wartości wejściowej (włącznie) i znaleźć liczbę, która daje najlepszy wynik przy użyciu powyższej formuły.


Wynik

Wynikiem będą dwie liczby oddzielone spacją, przecinkiem, znakiem nowej linii lub czymkolwiek innym językiem, na jaki pozwalasz (separacja jest niezbędna do rozróżnienia dwóch liczb). Można je wyprowadzić do pliku, standardowego wyjścia lub dowolnego innego języka. Twoim celem jest znalezienie liczby w zakresie, który daje maksymalną wydajność, gdy przejdziesz przez powyższą formułę. Pierwsza wyświetlana liczba powinna być liczbą początkową (np. 300), a druga liczba powinna stanowić wynik wygenerowany przez formułę (jak 262)


Przypadki testowe

Input: 3       Output: 2, -2
Input: 10      Output: 8, 4
Input: 50      Output: 48, 35
Input: 1000    Output: 1000, 971
Input: 9999    Output: 9984, 9802


Przepracowano przez przykład

Rozważ wprowadzenie 10, musimy uruchomić formułę dla wszystkich liczb od 2 do 10 (włącznie)

Num PrimeFacs PrimeFacs^2 SumPrimeFacs^2 Result
2   [2]       [4]         4              -2
3   [3]       [9]         9              -6
4   [2]       [4]         4               0
5   [5]       [25]        25             -20
6   [2, 3]    [4, 9]      13             -7
7   [7]       [49]        49             -42
8   [2]       [4]         4               4
9   [3]       [9]         9               0
10  [2, 5]    [4, 25]     29             -19

Jak widać, najlepszy wynik to 4wynik wprowadzenia wartości 8do formuły. Oznacza to, że wyjście 10powinno mieć wartość wejściową8, 4


Punktacja i zasady

Obowiązują domyślne zasady dla wejść i wyjść: Domyślne dla Code Golf: Metody wejścia / wyjścia
Zabronione są standardowe luki: Luki, które są domyślnie zabronione
Zgłoszenia mogą być funkcjami lub pełnymi programami

Najkrótszy kod w bajtach wygrywa

Keatinge
źródło
Naprawiłem kilka błędów ortograficznych i gramatycznych, a tytuł bardziej opisowy. Zmieniłem też nieco kwestię niedozwolania separatorów białych znaków, ponieważ najwyraźniej nie to miałeś na myśli (ponieważ znaki nowej linii i spacje są znakami białych znaków). Jeśli nie jest to zamierzenie, możesz cofnąć edycję i uczynić swój zamiar jaśniejszym.
Mego
2
Co powinno się stać, jeśli kilka liczb jest powiązanych w celu uzyskania maksymalnego wyniku?
Dennis
1
@Dennis czy mogę zaakceptować dowolną liczbę, która generuje maksymalny wynik? Nie chcę narzucać nowej reguły, która łamie wszystkie istniejące rozwiązania.
Keatinge
2
Tak, to prawdopodobnie najlepsza opcja. 950 może być przykładem, gdzie zarówno [900, 862], jak i [945, 862] byłyby prawidłowymi odpowiedziami.
Dennis
1
Wyjście mogę liczby w odwrotnej kolejności, np wejściowe 50: 35, 48?
nimi

Odpowiedzi:

4

Java 8 lambda, 247 239 233 225 224 219 198 161 znaków

Pomyślałem, że to musi być możliwe w przypadku mniej niż 300 znaków, ponieważ ... no wiesz ... Java!

I rzeczywiście jest to możliwe nawet w przypadku mniej niż 200 znaków!

m->{int n=1,u,f,F[],g,G=g=1<<31;for(;++n<=m;){u=n;F=new int[m+1];for(f=1;++f<=u;)u/=u%f<1?(F[f]=f--):1;f=0;for(int p:F)f+=p*p;g=n-f>g?(G=n)-f:g;}return G+","+g;}

Nie wiem, czy takie użycie importu jest uzasadnione, ale zakładam, że powinno być w porządku. Oto lambda nierozwinięta do klasy:

public class Q80507 {
    static String greatestAfterReduction(int maxNumber) {
        int number = 1, upper, factor, primeFactors[], greatestResult, greatestNumber = greatestResult = 1 << 31; // <-- Integer.MIN_VALUE;
        for (;++number <= maxNumber;) {
            // get unique primefactors
            upper = number;
            primeFactors = new int[maxNumber + 1];
            for (factor = 1; ++factor <= upper;)
                upper /= upper % factor < 1 ? (primeFactors[factor] = factor--) : 1;

            factor = 0;
            for (int prime : primeFactors)
                factor += prime * prime;

            greatestResult = number - factor > greatestResult ? (greatestNumber = number) - factor : greatestResult;
        }
        return greatestNumber + "," + greatestResult;
    }
}

Ustalenie pierwotnego czynnika opiera się na tej odpowiedzi . Kod wykorzystuje funkcjonalność zestawów, ponieważ zapisują każdą wartość tylko raz, więc nie muszę się już martwić o dodatkowe duplikaty. Reszta kodu jest dość prosta, po prostu po pytaniu.

Aktualizacje

Usunięto znak nowej linii z wyniku.

Dzięki @ogregoire za grę w golfa na liczbach całkowitych. MIN_VALUE do 1 << 31!

Po ponownym przejrzeniu kodu znalazłem jeszcze kilka miejsc, w których można grać w golfa.

Dzięki @Blue za lewę == 0 do <1!

Usunięto resztki białych znaków. Również do separacji potrzebny jest tylko jeden znak, więc nie musisz marnować jednego znaku.

Jeszcze raz dziękuję @ogregoire za wskazanie, że mogę zwrócić wartość zamiast wydrukować ją i złożyć deklaracje! To bardzo oszczędzało!

Dowiedziałem się, że mogę użyć trójki zamiast drugiej, aby zaoszczędzić jeszcze jeden znak.

Dzięki @AstronDan za niesamowite wykorzystanie tablicy, która oszczędza import. To dało mi również możliwość skrócenia pierwszego, jeśli do trójki.

Frozn
źródło
1
Integer.MIN_VALUEmożna skrócić jako 1<<31.
Olivier Grégoire
1
Zaoszczędź 1 bajt z if (u% f <1) zamiast tego
Blue
1
Zadeklaruj wszystkie swoje intw tym samym miejscu, aby uniknąć powtarzania ich intkilka razy, i przypisz im ich wartość, jeśli to możliwe.
Olivier Grégoire,
1
Pozbądź się tego System.out.println(...)i zwróć wartość zamiast go drukować: jak wspomina OP, używana jest standardowa metoda I / O.
Olivier Grégoire,
1
Możesz także użyć sztuczki tablicowej, której użyłem w języku C #, aby zmienić skrót w tablicę int. To prawdopodobnie pozwoli ci upuścić import, oszczędzając wiele bajtów.
AstroDan
3

Właściwie 21 bajtów

u2x;`;y;*@-`M;M;)@í@E

Wypróbuj online!

Wyjaśnienie:

u2x;`;y;*@-`M;M;)@í@E
u2x;                   push two copies of range(2, n+1) ([2, n])
    `      `M          map:
     ;                   duplicate
      y;                 push two copies of prime divisors
        *                dot product of prime divisors lists (equivalent to sum of squares)
         @-              subtract from n
             ;M;)      duplicate, two copies of max, move one copy to bottom of stack
                 @í    get index of max element
                   @E  get corresponding element from range
Mego
źródło
Czy możesz link do tego języka?
Nie, że Charles
1
@NotthatCharles Możesz kliknąć nazwę języka w tłumaczu online.
Dennis
Ok, przejrzałem Google Actually Programming Languagei nic nie znalazłem nawet po przejrzeniu 5. strony wyników Google. Co to za język?
Tejas Kale
2
@Tejas Możesz kliknąć nazwę języka, który wysłałby cię do źródła: github.com/Mego/Seriously
Amndeep7
3

MATL , 18 bajtów

:"@tYfu2^s-]v2#X>w

Wypróbuj online!

Ostatni przypadek kompilatora online trwa zbyt długo, ale daje poprawny wynik (zajmuje to około 11 sekund na moim komputerze, działającym na Matlabie):

enter image description here

Wyjaśnienie

Proste zastosowanie opisanej procedury.

:         % Implicit input n. Range [1 2 ... n]
"         % For each
  @       %   Push that number
  tYfu    %   Duplicate. Prime factors. Unique values
  2^s-    %   Square. Sum of array values. Subtract
]         % End for each
v         % Concatenate stack contents into vertical vector
2#X>      % Max and arg max
w         % Swap. Implicit display         
Luis Mendo
źródło
3

C #, 194 bajtów

Mój pierwszy Code Golf :). Użyłem mojego ulubionego języka pomimo jego gadatliwości. Zacząłem od tego jako portu funkcji C # w Javie @ Frozn, ale znalazłem kilka sposobów dalszego zmniejszenia kodu dzięki optymalizacji.

string R(int a){int u,f,g,N=g=1<<31;for(int n=1;++n<=a;){u=n;int[]P=new int[a+1];for(f=1;++f<=u;){if(u%f<1){u/=f;P[f]=f--;}}f=0;foreach(var p in P){f+=p*p;}if(n-f>g){g=(N=n)-f;}}return N+","+g;}

To używa tablicy do przechowywania czynników głównych. Ponieważ jest indeksowany przez czynnik, zastąpi powtarzające się czynniki kopiami tego czynnika. Dzięki temu funkcja nie ma importu. To nawet nie wymaga systemu.

AstroDan
źródło
To NAPRAWDĘ fajna sztuczka! Spróbuję użyć go w mojej wersji
Frozn
3

Narzędzia Bash + GNU, 74

seq 2 $1|factor|sed -r 's/:?( \w+)\1*/-\1*\1/g'|bc|nl -v2|sort -nrk2|sed q
  • seq generuje wszystkie liczby całkowite od 2 do n
  • factorpodaje liczbę, po której następuje dwukropek, a następnie rozdzieloną spacjami listę wszystkich czynników pierwszych, w tym duplikatów. np. wynik dla 12 to12: 2 2 3
  • sedusuwa dwukropek i duplikaty czynników, a następnie generuje wymagane wyrażenie arytmetyczne. np. dla 12:12- 2* 2- 3* 3
  • bc ocenia to
  • nl prefiksy n z powrotem (od 2)
  • sort według drugiej kolumny, numerycznie, w porządku malejącym
  • seq wypisuje pierwszą linię i wychodzi.

Ideone.

Cyfrowa trauma
źródło
2

Brachylog , 48 bajtów

:2:{eI$pd:{:2^.}a+:I--:I.}fF$\hor:0m:Ir.r~m[F:J]

Wyjaśnienie

Main predicate:

:2:{}fF                     Unify F with the list of all binding for which predicate 1 is
                            true, given [Input, 2] as input.
       $\hor:0m             Retrieve the max of F by diagonalizing it, taking the
                            first row, sorting that row and reversing the sorted row.
               :Ir.         Unify the Output with [I, Max],
                   r~m[F:J] [I, Max] is in F at index J (the index is unimportant)


Predicate 1:

eI                          I is an integer in the range given in Input
  $pd                       Get the list of prime factors of I, with no duplicates
     :{:2^.}a               Apply squaring to each element of that list
             +              Sum the list
              :I-           Subtract I from the sum
                 -          Multiply by -1 (let's call it Result)
                  :I.       Unify the Output with [Result, I]
Fatalizować
źródło
2

Galaretka , 13 bajtów

ÆfQ²S_@,µ€ḊṀṚ

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

ÆfQ²S_@,µ€ḊṀṚ  Main link. Argument: n

        µ      Combine the chain to the left into a link.
         €     Apply it to each k in [1, ..., n].
Æf               Yield k's prime factors as a list.
  Q              Unique; deduplicate the prime factors.
   ²             Square each unique prime factor.
    S            Compute their sum.
     _@          Subtract the result from k.
       ,         Pair with k, yielding [result(k), k].
          Ḋ    Dequeue; discard the first pair which corresponds to k = 1.
           Ṁ   Get the maximum (lexicographical order).
            Ṛ  Reverse the pair.
Dennis
źródło
2

05AB1E, 19 17 16 bajtów

Kod:

L©f€n€O®-®)ø¦{¤R

Wyjaśnienie:

L                    # make a list of 1..input [1,2,3,4,5,6]
 ©                   # save the list for reuse
  f                  # get primefactors of numbers in list [[],[2],[3],[2],[5],[2,3]]
   €n                # square each factor [[],[4],[9],[4],[25],[4,9]]
     €O              # sum the factors [0,4,9,4,25,13]
       ®-            # subtract from saved list [1,-2,-6,0,-20,-7]
         ®)ø         # zip with saved list [[1,1],[-2,2],[-6,3],[0,4],[-20,5],[-7,6]]
            ¦        # drop the first item (n=1) [[-2,2],[-6,3],[0,4],[-20,5],[-7,6]]
             {       # sort [[-20,5],[-7,6],[-6,3],[-2,2],[0,4]]
              ¤      # get last item [0,4]
               R     # reverse [4,0]

Wypróbuj online

Emigna
źródło
2

Julia, 56 bajtów

!n=maximum(k->(k-sumabs2(k|>factor|>keys),k),2:n)[[2,1]]

Wypróbuj online!

Jak to działa

Biorąc pod uwagę wartość wejściową n , dla każdej liczby całkowitej k takiej, że 2 ≤ k ≤ n , generujemy krotkę (f (k), k) , gdzie f (k) jest różnicą między k a sumą kwadratów jej czynników pierwszych .

f (k) oblicza się za pomocą tego k-sumabs2(k|>factor|>keys), który uwzględnia k w Dyktat liczb pierwszych i wykładników, wyodrębnia wszystkie klucze (czynniki pierwsze), pobiera sumę ich kwadratów i odejmuje wynikową liczbę całkowitą od k .

Na koniec bierzemy maksimum leksykograficzne wygenerowanych krotek i odwracamy je, uzyskując dostęp do wskaźników 2 i 1 .

Dennis
źródło
1

Clojure, 215 bajtów

(fn j[x](apply max-key second(map(fn[w][w(- w(let[y(reduce +(map #(* % %)(set(flatten((fn f[q](let[c(filter(fn[r](=(mod q r)0))(range 2 q))](if(empty? c)q(map f c))))w)))))](if(= y 0)(* w w)y)))])(range 2(inc x)))))

Po prostu przestrzega zasad. Oblicza czynniki pierwsze każdej liczby, oblicz je i zsumuj. Następnie wygeneruj listę wektorów 2 elementów: liczby początkowej i jej wyniku i znajdź element o maksymalnej wartości drugiego elementu.

Możesz to zobaczyć online tutaj: https://ideone.com/1J9i0y

Cliffroot
źródło
1

R 109 bajtów

y=sapply(x<-2:scan(),FUN=function(x)x-sum(unique(as.numeric(gmp::factorize(x))^2)));c(x[which.max(y)],max(y))

I oszukany i używane pakietu gmp.

Odbijająca się piłka
źródło
1

Pyke, 17 bajtów

FODP}mXs-)DSei@Oi

Wypróbuj tutaj!

niebieski
źródło
1

PowerShell v2 +, 124 120 117 bajtów

2..$args[0]|%{$y=$z=$_;2..$_|%{$y-=$_*$_*!($z%$_)*('1'*$_-match'^(?!(..+)\1+$)..')};if($y-gt$o){$o=$y;$p=$_}}
"$p $o"

Pierwszy wiersz oblicza wartości, drugi to tylko wynik.

Zaczynamy od utworzenia zakresu od 2naszego argumentu wiersza poleceń $args[0]i zapętlamy go |%{...}. W każdej pętli ustawiamy zmienne pomocnicze równe naszej bieżącej wartości $y=$z=$_. Następnie przeglądamy każdy numer od 2naszego obecnego numeru. W każdej wewnętrznej pętli sprawdzamy, czy liczba ta jest dzielnikiem !($z%$_)i czy jest liczbą pierwszą ('1'*$_-match'^(?!(..+)\1+$)..') , a jeśli obie, odejmujemy kwadrat $y(kontrole są wykonywane przy użyciu mnożenia logicznego).

Po przejściu przez wszystkie podstawowe dzielniki i odjęciu kwadratów, jeśli pozostała liczba jest największa, jaką widzieliśmy do tej pory $y-gt$o, ustawiamy nasze zmienne wyjściowe $o=$y;$p=$_. Po przejściu przez cały zakres po prostu wyprowadzamy z odstępem między.

AdmBorkBork
źródło
1

Haskell, 91 bajtów

f m=reverse$maximum[[n-sum[p^2|p<-[2..n],mod n p<1,mod(product[1..p-1]^2)p>0],n]|n<-[2..m]]

Przykład użycia: f 50-> [48,35].

Funkcje współczynnika głównego są dostępne tylko za pośrednictwem, import Data.Numbers.Primesktóre kosztują zbyt wiele bajtów, więc używam sprawdzania liczb pierwszych @ Lynn . Reszta jest prosta: dla wejścia mpętli nprzez [2..m]w wewnętrznej pętli pprzez [2..n]. Zachowaj wszystko, pco najważniejsze, dziel n, kwadrat i suma.

nimi
źródło
1

Python 2, 108 105 100 bajtów

f=lambda n,m=2,p=1:m>n or-~f(n,m+1,p*m*m)-(n%m<p%m)*m*m
r=max(range(2,input()+1),key=f)
print r,f(r)

Przetestuj na Ideone .

Dennis
źródło
1

JavaScript (ES6), 111 105 bajtów

f=n=>{r=n<2?[]:f(n-1);for(s=[],j=n,i=2;j>1;k%i?i++:j/s[i]=i);s.map(i=>j-=i*i,j=n);return j<r[1]?r:[n,j]}

Nie mam pojęcia, dlaczego wcześniej nie myślałem o tym rekurencyjnie.

Neil
źródło
1

J, 44 bajty

[:((],.~2+I.@e.)>./)@:}.1(-[:+/*:@~.@q:)@+i.

Proste podejście. Zwraca również wszystkie wartościn tego wyniku w maksymalnej wartości.

Stosowanie

   f =: [:((],.~2+I.@e.)>./)@:}.1(-[:+/*:@~.@q:)@+i.
   f 3
2 _2
   f 10
8 4
   f 50
48 35
   f 1000
1000 971
   f 9999
9984 9802
   f 950
900 862
945 862
mile
źródło