Naiki satu langkah ke yang terbaik

24

Judul video terbaru Numberphile , 13532385396179 , adalah titik tetap dari fungsi berikut f pada bilangan bulat positif:

Biarkan n menjadi bilangan bulat positif. Tulis faktorisasi prima dengan cara yang biasa, misalnya 60 = 2 2 · 3 · 5, di mana bilangan prima ditulis dalam urutan yang meningkat, dan eksponen 1 dihilangkan. Kemudian bawa eksponen ke bawah dan hilangkan semua tanda perkalian, dapatkan angka f (n). [...] misalnya, f (60) = f (2 2 · 3 · 5) = 2235.

(Definisi di atas diambil dari Masalah 5 dari Lima Masalah $ 1.000 - John H. Conway )

Perhatikan bahwa f (13532385396179) = f (13 · 53 2 · 3853 · 96179) = 13532385396179.

Tugas

Ambil bilangan bulat komposit positif nsebagai input, dan output f(n).

Contoh lain

48 = 2 4 · 3, jadi f (48) = 243.

Testcases

Lebih banyak testcases tersedia di sini .

   4 -> 22
   6 -> 23
   8 -> 23
  48 -> 243
  52 -> 2213
  60 -> 2235
 999 -> 3337
9999 -> 3211101
Biarawati Bocor
sumber
11
+1 Saya masih heran bahwa seseorang berhasil menemukan 13532385396179 sebagai pembongkaran dugaan. Saya kira hadiah $ 1000 akan digunakan untuk membayar listrik yang digunakan! :)
Wossname
7
Tanpa mengikuti tautan, tidak jelas bahwa dugaannya adalah bahwa aplikasi berulang dari f (n) akan selalu mencapai prime (dan tentu saja f (p) = p jika p adalah prime). 13532385396179 membantah dugaan itu karena keduanya komposit dan opint tetap.
Chris H

Jawaban:

16

Python, 166 162 159 byte

Kalian jauh lebih baik. Inilah yang saya gunakan! (Algoritma yang menyelesaikannya menyebutnya ini)

from primefac import*
def c(n):
 x=factorint(n)
 a=''
 for i in range(len(x)):
  l=min(x.keys())
  a+=str(l)
  if x[l]>1:a+=str(x[l])
  x.pop(l)
 return int(a)
jchd
sumber
2
Mengapa seseorang menurunkan orang baru daripada membantunya meningkatkan jawabannya seperti yang dilakukan @LeakyNun? :(
Shaggy
3
Maaf - itu benar-benar yang saya gunakan (saya menemukan nomornya). Saya hanya berpikir kode payah akan lucu. Anda bisa menjatuhkannya.
jchd
9
Selamat datang di situs ini. Senang sekali Anda berbagi dengan kami solusi Anda. (untuk orang yang tidak tahu, Jim Davis adalah orang yang memecahkan masalah ini sejak awal). Namun, jawaban atas tantangan perlu mengikuti beberapa aturan. Jika Anda hanya mengikuti saran dari @LeakyNun, maka jawaban Anda akan valid. (mungkin lihat jawaban lain untuk melihat seperti apa biasanya)
Dada
4
Ya Tuhan, saya tidak berharap Jim Davis sendiri muncul di situs ini, dan untuk menjawab tantangan saya ... Saya merasa sangat tersanjung sekarang ...
Leaky Nun
2
Ngomong-ngomong, bukan troll. Alamat email saya ada di gladhoboexpress.blogspot.ca/2014/10/climb-to-prime.html ... Saya meninggalkan posting, tidak ada yang membanjiri Anda dengan email karena matematika.
jchd
9

Brachylog , 8 byte

ḋoọc;1xc

Cobalah online!

Penjelasan

Example input: 60

ḋ          Prime decomposition: [5,3,2,2]
 o         Order: [2,2,3,5]
  ọ        Occurences: [[2,2],[3,1],[5,1]]
   c       Concatenate: [2,2,3,1,5,1]
    ;1x    Execute 1s: [2,2,3,5]
       c   Concatenate: 2235

Anda dapat menggunakan ℕ₂ˢ( pilih semua bilangan bulat yang lebih besar dari atau sama dengan 2 ) daripada ;1x, yang mungkin lebih mudah dibaca dan lebih dalam semangat Brachylog.

Fatalisasi
sumber
9

Jelly , 6 byte

ÆFFḟ1V

Cobalah online!

Penjelasan

ÆF      Get prime factorisation of input as prime-exponent pairs.
  F     Flatten.
   ḟ1   Remove 1s.
     V  Effectively flattens the list into a single integer.
Martin Ender
sumber
V= "digabungkan ke string tunggal dan eval sebagai Jelly"
Erik the Outgolfer
@EriktheOutgolfer Ya, karenanya "efektif".
Martin Ender
@ MartinEnder Ada alasan khusus yang tidak Anda gunakan (Konversi dari desimal ke integer)?
berhamburan
@Christian Karena daftar mungkin berisi bilangan bulat multi-digit.
Martin Ender
@ MartinEnder Ah, pintar. Saya telah menggunakan FḌdi masa lalu - itu tip yang bagus!
bubar
5

Mathematica, 43 36 Bytes

Row@Flatten@FactorInteger@#/. 1->""&

Cobalah online!

J42161217
sumber
2
DeleteCasespanjang, Anda dapat menggunakan /.1->""atau /.1->##&[](bentuk alternatif dari/.1->Nothing
user202729
3
@ user202729 Semua itu memerlukan ruang di depan 1untuk mencegah parsing ... / (0.1).
Martin Ender
Kamu benar! diperbaiki
J42161217
4

CJam , 8 byte

limF:~1-

Cobalah online!

Penjelasan

li  e# Read input and convert to integer.
mF  e# Get prime factorisation as prime-exponent pairs.
:~  e# Flatten.
1-  e# Remove 1s.
    e# Implicitly print a flattened representation of the list.
Martin Ender
sumber
Saya akan digunakan e_untuk meratakan, karena memang untuk itu, tetapi itu tidak mengubah skor.
Peter Taylor
1
@PeterTaylor Hm ya, saya tidak pernah bisa memutuskan yang mana yang akan digunakan, tetapi cenderung cocok dengan e_deep ratten saja dan digunakan :~setiap kali hanya satu level.
Martin Ender
4

05AB1E , 10 byte

Òγʒ¬?gDië?

Cobalah online!

Ò          # Push list of prime factors with duplicates
 γ         # Break into chunks of consecutive elements
  ʒ        # For each
   ¬?      #   Print the first element
     gD    #   Push the length of this chunk twice
       ië  #   If not 1
         ? #     Print the length
Riley
sumber
3

05AB1E , 12 11 byte

Òγvy¬sgD≠×J

Cobalah online!

Penjelasan

Ò            # calculate prime factors with duplicates
 γ           # group consecutive equal elements
  vy         # for each group
    ¬        # get the head without popping
     sg      # push the length of the group
       D≠×   # repeat the length (length != 1) times
          J  # join
Emigna
sumber
Gagal untuk 48.
Leaky Nun
2

Pyth, 12 byte

smjk_>hddr8P

Cobalah!

alternatif, 12 byte

smjk<_AdGr8P

Coba itu!

penjelasan

smjk_>hddr8P
           PQ  # prime factorization (already in correct order) of the implicit input: [3, 3, 11, 101]
         r8    # length encode: [[2, 3], [1, 11], [1, 101]]
 m             # map over the length encoded list (lambda variable: d)
     >hdd      # take the d[0] last elements of d (so only the last for d[0]==1 and all else)
    _          # reverse that list
  jk           # join into a string
s              # conatenate the list of strings
KarlKastor
sumber
2

Python 2 , 99 byte

n=input()
r=''
p=2
while~-n:
 e=0
 while n%p<1:e+=1;n/=p
 r+=str(p)*(e>0)+str(e)*(e>1);p+=1
print r

Cobalah online!

Jika input dibatasi di bawah 2147483659, keduanya str(...)dapat diganti dengan `...`menghemat 6 byte (program ini akan sangat lambat untuk angka yang terpengaruh!).

Jonathan Allan
sumber
2

Ohm , 11 byte

o:_]D2<?O;J

Cobalah online!

Penjelasan

o:_]D2<?O;J
o           # Push prime factors with powers from input (Format [[prime,power],...]
 :          # For each...
  _          # Push current element
   ]         # flatten
    D        # Duplicate power
     2<? ;   # Is the power smaller than 2?
        O     # Delete top of stacks
          J  # Join
Datboi
sumber
1

Japt , 19 byte

k ó¥ ®¯1 pZlÃc fÉ q

Uji secara online!

Penjelasan

 k ó¥  ®   ¯  1 pZlà c fÉ  q
Uk ó== mZ{Zs0,1 pZl} c f-1 q  // Ungolfed
                              // Implicit: U = input number
Uk                            // Break U into its prime factors.
   ó==                        // Group into runs of equal items.
       mZ{         }          // Map each item Z in this to
          Zs0,1               //   Z.slice(0, 1) (the array of the first item),
                pZl           //   with Z.length added at the end.
                              // This returns an array of prime-exponent pairs (Jelly's ÆF).
                     c        // Flatten.
                       f-1    // Filter to the items X where X - 1 is truthy (removes '1's).
                           q  // Join the resulting array into a single string.
                              // Implicit: output result of last expression
Produksi ETH
sumber
1

PHP , 88 byte

for($i=2;1<$a=&$argn;)$a%$i?$i++:$a/=$i+!++$r[$i];foreach($r as$k=>$v)echo$k,$v<2?"":$v;

Cobalah online!

Jörg Hülsermann
sumber
0

C #, 206 100 byte

n=>{var r="";for(int d=1,c;++d<=n;){c=0;while(n%d<1){c++;n/=d;}r+=c>0?d+(c>1?c+"":""):"";}return r;}

Versi Lengkap / Terformat:

using System;

class P
{
    static void Main()
    {
        Func<int, string> func = n =>
        {
            var r = "";
            for (int d = 1, c; ++d <= n;)
            {
                c = 0;
                while (n % d < 1)
                {
                    c++;
                    n /= d;
                }

                r += c > 0 ? d + (c > 1 ? c + "" : "") : "";
            }

            return r;
        };

        Console.WriteLine(func(4));
        Console.WriteLine(func(6));
        Console.WriteLine(func(8));
        Console.WriteLine(func(48));
        Console.WriteLine(func(52));
        Console.WriteLine(func(60));
        Console.WriteLine(func(999));
        Console.WriteLine(func(9999));

        Console.ReadLine();
    }
}
TheLethalCoder
sumber
0

Javascript - 91 byte

(x,r='',i=1,n)=>{while(x>i++){for(n=0;x%i<1;n++)x/=i;r+=(n>0?i+'':'')+(n>1?n:'')}return r}

Penjelasan

(x,r='',i=1,n)=>(          // input x is the number to process, r, i, n are default values only
    while(x>i++){          // iterate over i until x
        for(n=0;x%i<1;n++) // iterate over n until i is not a factor of x
            x/=i;          // factor i out of x
        r+=(n>0?i+'':'')   // append i to r if n > 0
            +(n>1?n:'')    // append n to r if n > 1
                           // i+'' prevents adding i and n before appending to r
    }
    return r               // return r by comma-operator and arrow function syntax
)
sangat penting
sumber
0

Java 8, 103 karakter

Solusi yang sangat mudah.

n->{String r="";int d=2,c;while(n>1){c=0;while(n%d<1){c++;n/=d;}if(c>0)r+=d;if(c>1)r+=c;d++;}return r;}

Tidak Disatukan:

private static Function<Integer, String> f = n->{
    String result = "";
    int divisor = 2, count;
    while (n>1) {
        count = 0;
        while (n % divisor < 1) {
            count++;
            n /= divisor;
        }
        if (count > 0) result += divisor;
        if (count > 1) result += count;
        divisor++;
    }
    return result;
};
Computronium
sumber
91 byte
ceilingcat
0

Oktaf , 69 byte

@(a)printf('%d',(f=[[~,c]=hist(b=factor(a),d=unique(b));d](:))(f~=1))

Cobalah online!

Akhirnya menjadi cukup lama, tetapi ini akan menghasilkan output yang diinginkan.

Pada dasarnya kami menggunakan fungsi histogram untuk menghitung jumlah kemunculan dari nilai-nilai unik dalam faktorisasi utama dari nilai input.

  • Hasil factor()fungsi memberikan faktor prima dalam urutan menaik
  • kami kemudian menemukan unique()nilai dalam array itu
  • hist() mengembalikan jumlah kejadian

Setelah kami memiliki dua array (satu untuk faktor unik, satu untuk jumlah), kami menggabungkan array secara vertikal (satu di atas yang lain), dan kemudian meratakan. Ini interleaves faktor dengan jumlah.

Akhirnya kami menampilkan hasilnya sebagai string yang memastikan untuk melewatkan 1 di array terakhir. Satu-satunya waktu 1 dapat muncul adalah jika hitungannya 1 karena 1 tidak akan pernah menjadi faktor utama. Penghapusan ini dilakukan sebelum mengkonversi ke string sehingga tidak akan mempengaruhi hal-hal seperti angka 10.

Tom Carpenter
sumber
0

Ruby , 45 + 7 byte

Membutuhkan bendera -rprime.

->n{(n.prime_division.flatten-[1]).join.to_i}

Cobalah online!

canhascodez
sumber
0

Pyth - 16 byte

V{PQpNK/PQNItKpK

Cobalah

Solusi lain:

sm`d-.nm(d/PQd){PQ1
Maria
sumber
1
Satu dapat digantikan FNoleh V.
Leaky Nun
1
Juga, r8(run-length encoding) tampaknya bermanfaat.
Leaky Nun
0

R , 72 byte

x=rle(pracma::factors(scan()));x$l[x$l<2]='';paste0(x$v,x$l,collapse='')

Membutuhkan pracmapaket, yang tidak diinstal pada TIO.

Giuseppe
sumber