Znajdź super palindromy!

23

Zastanów się nad liczbą 99999999. Liczba ta jest oczywiście palindromem. Największy czynnik pierwszy wynoszący 99999999 wynosi 137. Jeśli podzielisz 99999999 przez 137, otrzymasz 729927. Liczba ta jest również palindromem.

Największy czynnik pierwszy wynoszący 729927 wynosi 101. 729927/101 = 7227, co znowu jest palindromem.

Największy czynnik pierwszy wynoszący 7227 wynosi 73. 7227/73 = 99, co znowu jest palindromem.

Przez dalsze dzielenie przez największy czynnik pierwszy, otrzymujesz 9, 3 i ostatecznie 1, które, będąc liczbami jednocyfrowymi, są również palindromami. Ponieważ 1 nie ma czynników pierwszych, procedura kończy się tutaj.

Teraz uogólniając to spostrzeżenie, definiuję super-palindrom jako palindrom, który ma wartość 1 lub daje inny super-palindrom, jeśli jest podzielony przez jego największy czynnik pierwszy.

Kredyty: /math/200835/are-there-infinitely-many-super-palindromes

Biorąc pod uwagę liczbę N , określ, czy jest to superpalindrom, czy nie, i wydrukuj odpowiednio wartość prawdy lub falseya.

Twój program powinien wydrukować prawdziwą wartość dla tych danych wejściowych:

1
101
121
282
313
353
373
393
474
737
919
959
1331
1441
2882
6446
7887
8668
9559
9779

Twój program powinien wydrukować wartość falsey dla tych danych wejściowych:

323
432
555
583
585
646
642
696
777
969
989
2112
3553
4554
5242
5225
5445
8080
8118
9988

Pamiętaj, że to jest , więc wygrywa kod z najmniejszą ilością bajtów.

Oliver Ni
źródło
3
Czy dane wejściowe Nzawsze będą palindromem na początek?
Sherlock9
@ Sherlock9 No ..
Oliver Ni
2
W takim razie czy możesz dodać nie-palindromy do przypadków testowych falsey? Wyjaśniłoby to specyfikację.
Sherlock9

Odpowiedzi:

8

Galaretka , 13 12 9 8 bajtów

Æf×\D⁼U$

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

Æf×\D⁼U$  Main link. Argument: n

Æf        Yield all prime factors of n, with multiplicities and in ascending order.
  ×\      Take the cumulative product.
    D     Decimal; convert each product into the array of its base 10 digits.
       $  Combine the two links to the left into a monadic chain.
      U     Upend; reverse all arrays of decimal digits.
     ⁼      Test for equality.
Dennis
źródło
6

Mathematica, 64 bajty

And@@PalindromeQ/@FixedPointList[#/FactorInteger[#][[-1,1]]&,#]&

Funkcja bez nazwy, zwracana Truelub False. Tworzy listę, zaczynając od wejścia, a następnie iterując funkcję „ja podzielony przez mój największy współczynnik pierwszy”, aż wynik się nie zmieni. (Na szczęście Mathematica uważa teraz, że największy czynnik pierwszy wynoszący 1 wynosi 1.) Następnie sprawdza, czy wpisy na liście są palindromami (tak, wbudowane! Długość nazwy funkcji boo!) I Ands je wszystkie razem.

Greg Martin
źródło
Zgrabna sztuczka (ab) przy użyciu FactorInteger[1]osobliwości zFixedPoint
LegionMammal978
tak, choć raz pomogło! :)
Greg Martin
6

Mathematica, 51 bajtów

#<2||PalindromeQ@#&&#0[#/FactorInteger[#][[-1,1]]]&

Rekurencyjna anonimowa funkcja. Pobiera liczbę jako dane wejściowe i zwraca Truelub Falsedane wyjściowe.

LegionMammal978
źródło
6

05AB1E , 9 8 bajtów

Oszczędność bajtu dzięki Adnanowi .

Ò.pPDíïQ

Wypróbuj online!

Wyjaśnienie

n = 7227 użyty jako przykład

Ò           # prime factors with duplicates
            # STACK: [3, 3, 11, 73]
 .p         # prefixes
            # STACK: [[3], [3, 3], [3, 3, 11], [3, 3, 11, 73]]
   P        # product
            # STACK: [3, 9, 99, 7227]
    D       # duplicate
            # STACK: [3, 9, 99, 7227], [3, 9, 99, 7227]
     í      # reverse each
            # STACK: [3, 9, 99, 7227], ['3', '9', '99', '7227']
      ï     # convert to  int
            # STACK: [3, 9, 99, 7227], [3, 9, 99, 7227]
       Q    # check for equality
            # STACK: 1
            # implicit output
Emigna
źródło
Myślę, że Ò.pPDíïQrównież powinien działać.
Adnan
5

Pyth - 15 12 bajtów

Pokonaj galaretkę: P : /

Niestety, wszystkie te niejawne mapy nie stają się krótsze, gdy są połączone w wyraźną, ponieważ ostatnia jest auto-splat.

.A_IM`M*M._P

Pakiet testowy .

Pobiera wszystkie prefiksy pierwszej faktoryzacji, których produktami będą pośrednie superpalindromy i sprawdza, czy wszystkie z nich są palindromami.

Maltysen
źródło
4

Mathematica, 71 63 bajtów

And@@PalindromeQ/@FoldList[1##&,Join@@Table@@@FactorInteger@#]&

Wyjaśnienie

FactorInteger@#

Uwzględnij dane wejściowe. (np. 8668 -> {{2, 2}, {11, 1}, {197, 1}}dla każdej listy w danych wyjściowych pierwszym elementem jest czynnik pierwszy, a drugim moc.

Join@@Table@@ ...

Dla każdej pary czynnik-moc powiel pierwszy element przez drugi element i spłaszcz całą rzecz. ( {{2, 2}, {11, 1}, {197, 1}} -> {{2, 2}, {11}, {197}} -> {2, 2, 11, 197})

FoldList[1##&, ... ]

Iteruj po liście, mnożąc elementy. ( {2, 2, 11, 197} -> {2, 2 * 2, 2 * 2 * 11, 2 * 2 * 11 * 197} -> {2, 4, 44, 8668})

And@@PalindromeQ/@ ...

Sprawdź, czy wszystkie wynikowe liczby są palindromami, i zastosuj Andoperator. ( {2, 4, 44, 8668} -> {True, True, True, True}-> True)

JungHwan Min
źródło
oooo, ładnie zrobione! Teraz muszę sprawdzić, czy mogę gdzieś zapisać 2 bajty ...
Greg Martin,
3

Brachylog , 14 bajtów

1|r?$ph:?r/:0&

Wypróbuj online!

Wyjaśnienie

To implementuje formułę wyjaśnioną w opisie wyzwania.

Obliczenie wszystkich produktów sufiksów pierwszego rozkładu i sprawdzenie, czy wszystkie są palindromami, trwa 1 bajt dłużej ( 1|$p:@]f:{*.r}a).

1                  Input = 1
 |                 OR
  r?               Reversing the Input results in the Input
    $p             Get the prime factors of the Input
      h            Take the first one (the biggest)
       :?r/        Divide the Input by that prime factor
           :0&     Call this predicate recursively with that new number as input
Fatalizować
źródło
2

Rakieta 238 bajtów

(define(p n)(=(string->number(list->string(reverse(string->list(number->string n)))))n))
(if(= n 1)#t(begin(let o((n n))(define pd(prime-divisors n))(if(null? pd)#f(begin(let((m(/ n(last pd))))
(cond[(= m 1)#t][(p m)(o m)][else #f])))))))

Nie golfowany:

(define (f n)
  (define (palin? n)                      ; define palindrome of number
    (=(string->number
       (list->string
        (reverse
         (string->list
          (number->string n)))))
      n))
  (if(= n 1)#t
     (begin
       (let loop ((n n))
         (define pd (prime-divisors n))   ; find prime divisors
         (if (null? pd) #f                ; end if none- not superpalindrome
             (begin
               (let ((m (/ n (last pd)))) ; divide by largest prime divisor
                 (cond                    ; test quotient
                   [(= m 1) #t]           ; end if 1: super-palindrome found
                   [(palin? m) (loop m)]  ; loop with quotient if palindrome
                   [else #f]              ; end if not palindrome
                   ))))))))

Testowanie:

(f 1)
(f 101)
(f 121)
(f 282)
(f 313)
(f 353)
(f 373)
(f 393)
(f 474)
(f 737)
(f 919)
(f 959)
(f 1331)
(f 1441)
(f 2882)
(f 6446)
(f 7887)
(f 8668)
(f 9559)
(f 9779)
(f 99999999)

Wydajność:

#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
#t
rnso
źródło
Rakieta nie jest mi znana, ale czy konieczne jest, aby twoja funkcja pomocnicza palinmiała pięciobajtową nazwę?
Roman Gräf
Poprawiłem go wcześniej, ale nie wkleił się tutaj poprawnie. 238 bajtów to nazwa „p”. Dzięki za wskazanie.
rnso
2

J, 30 bajtów

0:`(%1>.{:@q:)@.((-:|.)@":)^:_

Błąd dla falsey, 1 dla prawdy.

Pierwsza próba, nie błędu dla falsey, 40 bajtów:

0:`(([:$:]%{:@q:)`[@.(1&=))@.((-:|.)@":)

Wyjaśnienie

0:`(%1>.{:@q:)@.((-:|.)@":)^:_
                           ^:_  repeat until convergent
              @.((-:|.)@":)     if the number is palindromic:
   (         )                   do the stuff inside, which is a 4-train
        {:@q:                    largest prime factor
     1>.                         (or 1, if smaller than 1)
    %                            divide the original number by this value
0:`                             otherwise, return 0
                                (because of ^:_, this will be passed into q:, which will
                                error because 0 cannot be factored.)

Przypadki testowe

   NB. collect errors; 0 if errored, otherwise the result of the function
   NB. left arg: values; right arg: boxed name of function
   errors =: 4 : 0
    f =. y`:6
    l =: ''
    for_e. x do.
        try.
            l =. l , f e
        catch.
            l =. l , 0
        end.
    end.
    l
)
   s =: 0:`(%1>.{:@q:)@.((-:|.)@":)^:_
   t =: 1 101 121 282 313 353 373 393 474 737 919 959 1331 1441 2882 6446 7887 8668 9559 9779
   f =: 323 432 555 583 585 646 642 696 777 969 989 2112 3553 4554 5242 5225 5445 8080 8118 9988
   t ,. f
   1  323
 101  432
 121  555
 282  583
 313  585
 353  646
 373  642
 393  696
 474  777
 737  969
 919  989
 959 2112
1331 3553
1441 4554
2882 5242
6446 5225
7887 5445
8668 8080
9559 8118
9779 9988
   (t ,. f) errors"1 0 <'s'
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
Conor O'Brien
źródło
2

아희 (Aheui) , 309 bajtów (100 znaków * 3 bajty + 9 znaków nowej linii)

방빩반룸있쁏멐솔쌀잌
앟놂숙참뿔썁썸뻙솝셜
본서번분번뮴딸냥별쀼
슉눇번낢퉅쑫썬쌀본묳
뽇서본석첫삭뽑롷떵춤
분촐럶사눙읽숟뗘분뻨
듐삭빶쏘윙잉썩손뵬괆
쌰뭉쇼텰궮변번첳웅텩
뽇흶아희쾯볻훼윺엄솝
코드골프욉쁍숙쌉삼쏩

Jestem tak szczęśliwy, że właściwie to skończyłem!

Jestem nowy w tym języku, więc mile widziane są wszelkie wskazówki dotyczące zwiększania liczby bajtów.

Wypróbuj tutaj! (skopiuj i wklej kod)

Wersja czystsza

방빠반루ㅇ쀼머솔쌀이
아노숙차뿌썁썸뻐솝셜
본서번분번뮤따냐별쀼
슉누번나투쑫썬쌀본묘
뽀서본석처삭뽀로떠추
분초러사누이숟뗘분뻐
듀삭빠쏘ㅇ이썩손뵬ㅇ
쌰뭉쇼텨이변번처우텨
뽀희ㅇㅇㅇ볻ㅇ유어솝
ㅇㅇㅇㅇㅇㅇ숙쌉삼쏩
JungHwan Min
źródło
Jaka jest różnica między wersją normalną a wersją czystszą?
Oliver Ni
@Oliver Pierwsza wersja nie ma NOP (ㅇ) i ma bardziej złożone znaki (są identyczne, tylko pierwsza sprawiła, że ​​wyglądała bardziej ezoterycznie). Druga wersja jest dla tych, którzy chcieliby przeczytać program, bez wszystkich bełkotów.
JungHwan Min.
0

Scala, 138 bajtów

def?(n:Int):Int={val p=Stream.from(2).filter(n%_==0)(0)
if(p==n)n else?(n/p)}
def s(i:Int):Boolean=i<2||(i+"")==(i+"").reverse&&s(i/ ?(i))

Nie golfowany:

def largestFactor(n:Int):Int={
  val p=Stream.from(2).filter(n%_==0).head
  if(p==n)n else largestFactor(n/p)}
def superPalindrome(i:Int):Boolean=i<2||(i+"")==(i+"").reverse&&superPalindrome(i/ largestFactor(i))

Wyjaśnienie:

def?(n:Int):Int={                       //define a method for the largest prime factor
  val p=Stream.from(2).filter(n%_==0)(0)  //find the first factor of n
  if(p==n)n else?(n/p)                    //if it's n, return n else the next factor
}
def s(i:Int):Boolean=                     //method for the superprime
  i<2                                     //if s<2 return true
  ||                                      //else return:
    (i+"")==(i+"").reverse                  //is i a palindrome
    &&                                      //and
    s(i/ ?(i))                              //is i divided by it's largestPrimeFactor a superpalindrome
corvus_192
źródło
0

JavaScript (ES6), 78 bajtów

(n,d=2,p=1)=>n%d?n<2||f(n,d+1,p):[...p=p*d+''].reverse().join``==p&&f(n/d,d,p)

Rekurencyjnie buduje główne prefiksy faktoryzacji i sprawdza je pod kątem palindromiczności.

Neil
źródło
0

Java 7, 133 bajty

int c(int a){int x=a,y=0,z=a,i=2;for(;x>0;y=y*10+x%10,x/=10);for(;z>1;i++)for(;z%i<1;z/=i);if(a<2)return 1;return y!=a?0:c(a/(i-1));}

Bez golfa

    static int c( int a ){
    int x = a , y = 0 , z = a , i = 2 ;

    for ( ; x > 0 ; y = y * 10 + x % 10 , x /= 10 ) ;

    for ( ; z > 1 ; i++ )
    for ( ; z % i < 1 ; z /= i ) ; 

    if ( a < 2 )
      return 1 ;

    return y != a ? 0 : c( a / ( i - 1 ) ) ;       
 }
Numberknot
źródło
0

Tak właściwie 29 bajtów

Prawdopodobnie istnieje kilka sekcji tego kodu, które można by zagrać w golfa, choć nie jestem jeszcze pewien, gdzie. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

╗1`X╜$;R=;╝╜yN╜\;╗1<&`╬X╜DY╛&

Ungolfing

          Implicit input n.
╗         Save n to register 0.
1`...`╬   Run the following function on the stack while TOS is truthy.
  X         Discard the previous truthy.
  ╜         Push n from register 0.
  $         Push str(n).
  ;R=       Check if str(n) == str(n)[::-1], i.e. if n is a palindrome.
  ;╝        Save a copy of (is n a palindrome?) to register 1.
  ╜yN       Get the largest prime factor of n.
  ╜\        Divide n by its largest prime factor.
  ;╗        Save a copy of n // l_p_f to register 0.
  1<        Check if 1 < n // l_p_f. This returns 0 only if n // l_p_f is 1.
  &         Logical AND (is n a palindrome?) and (is n // l_p_f > 1?).
            This quits if we have reached a non-palindrome or we have reached 1.
X         Discard the falsey that ended the previous function.
╜         Get the last value saved to register 0 (could be 1 or a non-palindrome // l_p_f)
DY        This returns 1 if register 0 was a 1, else 0.
╛&        Logical AND with register 1 (was the last n a palindrome?) to get our result.
          Implicit return.
Sherlock9
źródło