รากฐานที่สำคัญของระบบ

Gryphon 10/04/2017. 18 answers, 1.017 views
code-golf number sequence primes

แรงบันดาลใจจากรากดิจิทัลรากปัจจัยสำคัญของจำนวนคือจำนวนที่เกิดขึ้นเมื่อคุณใช้ปัจจัยสำคัญของตัวเลขเพิ่มเข้าด้วยกันและทำซ้ำขั้นตอนกับจำนวนที่เป็นผลลัพธ์ให้ดำเนินต่อไปจนกว่าคุณจะจบลงด้วยตัวเลขที่สำคัญ ( ที่มีตัวมันเองเป็นปัจจัยสำคัญเพียงอย่างเดียวและเป็นรากฐานของตัวเองที่สำคัญของตัวเอง) รากปัจจัยที่สำคัญของ 4 คือ 4 เป็น 2 * 2 = 2 + 2 และนี่คือรากปัจจัยที่สำคัญเฉพาะของจำนวนเต็มมากกว่า 1 (ซึ่งเป็นอีกกรณีพิเศษเนื่องจากไม่มีปัจจัยสำคัญ) ลำดับ OEIS ที่สร้างขึ้นโดยรากฐานที่สำคัญคือ A029908

ตัวอย่างเช่นรากปัจจัยที่สำคัญของ 24 คือ:

24=2*2*2*3

2+2+2+3=9=3*3

3+3=6=2*3

2+3=5, and the only prime factor of 5 is 5.  Therefore, the prime factoral root of 24 is 5. 

งานของคุณ:

เขียนโปรแกรมหรือฟังก์ชันที่พบว่าเป็นรากฐาน factoral ที่สำคัญของจำนวนเต็ม input

การป้อนข้อมูล:

จำนวนเต็มป้อนข้อมูลผ่านวิธีการที่เหมาะสมใด ๆ ระหว่าง 2 และจำนวนเต็มที่ใหญ่ที่สุดที่ภาษาของคุณจะสนับสนุน (รวม) โดยเฉพาะการเลือกภาษาที่มีขนาดจำนวนเต็มสูงสุดต่ำสุดที่ไม่สมควรจะไม่ได้รับอนุญาต (และยังเป็นการละเมิด ทางหนีที่เป็นมาตรฐาน )

เอาท์พุท:

จำนวนเต็มรากปัจจัยที่สำคัญของการป้อนข้อมูล

กรณีทดสอบ:

4   -> 4
24  -> 5
11  -> 11
250 -> 17 

เกณฑ์การให้คะแนน:

นี่เป็น คะแนนต่ำสุดที่ชนะไบต์!

5 Comments
3 scottinet 10/04/2017
คุณสามารถเพิ่ม 4 ในกรณีทดสอบเนื่องจากเป็นข้อยกเว้นและเป็นเรื่องง่ายที่จะลืมเกี่ยวกับมันในขณะที่การทดสอบคำตอบ?
someone 10/04/2017
เราต้องส่งออก 1 สำหรับ 1 หรือไม่?
scottinet 10/04/2017
@ คนหนึ่งตามลำดับ OEIS ที่เชื่อมโยงควรส่งออก 0 เป็นเวลา 1
2 Martin Ender♦ 10/04/2017
ใครบางคนความท้าทายระบุว่าอินพุตจะมีอย่างน้อย 2
Gryphon 10/05/2017
@someone ขออภัยในการปิดสักครู่ เป็น Martin กล่าวว่าความท้าทายโดยเฉพาะกล่าวว่า input จะมากกว่าหนึ่งและดังนั้นพฤติกรรมเมื่อใส่เป็น 1 จะไม่ได้กำหนด

18 Answers


scottinet 10/04/2017.

05AB1E , 3 ไบต์

FÒO 

ทดลองใช้แบบออนไลน์!

Explanations:

FÒO   
F    Loops  times + 1
 Ò   List of prime factors w/ duplicates
  O  Total sum of the list
     -- implicit output 
5 comments
Shaggy 10/04/2017
นี้ดูเหมือนจะล้มเหลวสำหรับ 4
scottinet 10/04/2017
@Shaggy คงที่พร้อมประหยัด 2 ไบต์
8 caird coinheringaahing 10/04/2017
+1 สำหรับโค้ดที่เป็น FOO
7 steenbergh 10/04/2017
นี้ทำให้ทุกคนพยายามที่จะเอาชนะนักรบ FIA?
Magic Octopus Urn 10/04/2017
อย่างน้อยก็ไม่ใช่ FOObar

Laikoni 10/05/2017.

Haskell , 61 ไบต์

 import Data.Numbers.Primes
until=<<((==)=<<)$sum.primeFactors 

ทดลองใช้แบบออนไลน์!

คำอธิบาย

until=<<((==)=<<) ใช้ฟังก์ชัน f และนำไปใช้กับ x จนกว่าจะถึงจุดที่กำหนดคือ f x เท่ากับ x primeFactors ส่งกลับรายการปัจจัยที่สำคัญของจำนวน sum ผลรวมของรายการของตัวเลข

But wait, why does until=<<((==)=<<) the job and looks so weird?

ถ้าสมมุติ f=sum.primeFactors ความหมายที่เป็นไปตามธรรมชาติจะเป็น until(\x->f x==x)f ได้ until(\x->f x==x)f เพราะ until จะใช้ predicate (ฟังก์ชันที่ส่งกลับค่า boolean) ฟังก์ชันที่มีอินพุตเดียวกันและ return type (เช่น Int -> Int ) และค่าของชนิดนี้จากนั้นให้ใช้ฟังก์ชันนี้กับค่าจนกว่าจะมีการเติมคำร้อง

until(\x->f x==x)f เป็นค่าเท่ากัน until(\x->(==)(f x)x)f และเมื่อมันถือได้ว่า g (h x) x จะเหมือนกับ (g=< , we get until(\x->((==)=< . หลังจาก การแปลง ETA นี้จะกลายเป็น until((==)=< . แต่ถ้าตอนนี้เราถือว่า (==)=<< เป็นฟังก์ชันที่ใช้กับ f เราจะเห็นได้ว่า until(((==)=<<)f)f เป็นอีกรูปแบบ g (h x) x , กับ g=until , h=((==)=<<) และ x=f ดังนั้นจึงสามารถเขียนใหม่ได้ (until=<<((==)=<<))f . ใช้ตัวดำเนินการ $ เพื่อกำจัดวงเล็บด้านนอกและแทนที่ f ด้วย sum.primeFactors จะให้โซลูชันจากด้านบน

2 comments
i cri everytim 10/05/2017
=<<((==)=<<)$ Whaaaaaat
Laikoni 10/05/2017
@icrieverytim ฉันเพิ่มคำอธิบาย คุณสามารถถามได้ใน ห้องสนทนาของ Haskell หากคุณมีข้อสงสัยเพิ่มเติมเกี่ยวกับวิธีการใช้เวทมนตร์นี้

Laikoni 10/04/2017.

แกลบ 4 ไบต์

ω(Σp 

ทดลองใช้แบบออนไลน์!

คำอธิบาย:

ω(   -- apply the following function until the result no longer changes (fixpoint)
  Σ  -- sum
   p -- the list of primefactors 

Kevin Cruijssen 10/05/2017.

Java 8, 175 144 142 141 bytes

 n->{for(int i,t=n,x;;n=t){for(i=2;i1|n<5)return n;for(t=0,i=1;i++9;x/=10)t+=x%10;}} 

ขอบคุณ 1 ไบต์ที่ @Nevay

แตกต่างจากไบต์เดี่ยวในบางภาษากอล์ฟ Java เป็น verbose สวยสำหรับนายกรัฐมนตรีตรวจสอบปัจจัยสำคัญตัวเลขผลรวมและดังนั้นฉันเดาน้อยกว่า 200 ไม่โทรมเกินไป
อาจยังคงเล่นกอล์ฟได้โดยการรวมลูป และไม่ใช้วิธีการ recursive แบบแยกตัวสำหรับผลรวมหลัก

Explanation:

ลองใช้ที่นี่

 n->{                // Method with integer as both parameter and return-type
  for(int i,        //  Index-integer `i`
          t=n,      //  Temp integer `t`, starting at the input `n`
          x;        //  Temp integer `x`
      ;             //  Loop (1) indefinitely
      n=t){         //    After every iteration, replace `n` with the value `t`
    for(i=2;        //   Reset `i` to 2
        i1          //   If `t` is not 0 (it means it's a prime),
       |n<5)        //   or if `n` is below 5 (for edge-cases `4` and 'prime' `1`)
      return n;     //    Return `n` as result
    for(t=0,        //   Reset `t` to 0
        i=1;        //   Reset `i` to 1
        i++9;    //     Inner loop (5) as long as `x` contains more than 1 digit
            x/=10)  //       After every iteration, remove the trailing digit
          t+=n%10;  //      Increase `t` with the trailing digit of `n`
                    //     End of inner loop (5) (implicit / single-line body)
                    //    End of inner loop (4) (implicit / single-line body)
                    //   End of inner loop (3) (implicit / single-line body)
  }                 //  End of loop (1)
}                   // End of method 
5 comments
3 someone 10/04/2017
+1 สำหรับการรบกวนการเขียนคำอธิบายเป็น verbose เช่นถ้าเป็นภาษากอล์ฟ
Kevin Cruijssen 10/04/2017
ขอบคุณใครสักคน! ตั้งแต่มีคนถามผมเกี่ยวกับคำอธิบายของคำตอบ Java ของฉันเมื่อในอดีตที่ผ่านมาฉันได้รับการเพิ่มให้คำตอบของฉันทั้งหมด :)
ETHproductions 10/04/2017
i,t=n,x ดูเหมือนว่ามันเป็นของ Python, haha
Kevin Cruijssen 10/04/2017
@ETHproductions Hehe, แย่มากฉันยังคงต้องเพิ่ม int ชั้นนำ (ไม่เหมือนกับ Python) ;)
Nevay 10/04/2017
คุณสามารถใช้ i++ แทน ++i<=n

someone 10/04/2017.

เยลลี่ 5 ไบต์

ÆfS$¡ 

คำอธิบาย:

Æf    list of prime factors
  S   sum
   $¡ repeat n times 

ทดลองใช้แบบออนไลน์!

2 comments
someone 10/04/2017
ขอบคุณ กำลังมองหาที่สำหรับในขณะที่

Erik the Outgolfer 10/04/2017.

Pyth , 3 ไบต์

usP 

ลองใช้ที่นี่

คำอธิบาย:

usPGQ The trailing GQ is implicit
  PG  Get prime factors
 s    Sum
u   Q Repeat until returned value no longer unique starting with the input 

Martin Ender 10/04/2017.

Retina , 30 ไบต์

{+`(\1|\b11+?\B)+$
$1;$#1$*
; 

อินพุตและเอาต์พุตใน เอก

ทดลองใช้แบบออนไลน์! (ทำการแปลงทศนิยม / แปลงตัวเองเพื่อความสะดวก)

คำอธิบาย

{+`(\1|\b11+?\B)+$
$1;$#1$* 

{ สั่ง Retina ให้รันโปรแกรมทั้งหมดในลูปจนกว่าการส่งแบบเต็มจะไม่สามารถแก้ไขสตริงได้เช่นจนกว่าจะถึงจุดที่กำหนดไว้ ดังนั้นโปรแกรมเองคำนวณหนึ่งขั้นตอนของการสรุปปัจจัยสำคัญของค่าปัจจุบัน

ขั้นตอนนี้เองคำนวณ factorisation สำคัญของการป้อนข้อมูล + คล้ายกับ { แต่จะวนเฉพาะขั้นตอนนี้จนกว่าจะหยุดการเปลี่ยนสตริง regex พยายามจับคู่การทำงานสุดท้ายของ 1 วินาทีโดยจับคู่สายอักขระย่อยเดียวกันซ้ำ ๆ (เช่นตัวประกอบ) วิธีการนี้ทำได้ค่อนข้างซับซ้อนเนื่องจากการอ้างอิงไปข้างหน้า \1 ในการทำซ้ำครั้งแรกกลุ่ม 1 ยังไม่ได้บันทึกอะไรดังนั้น \1 ไม่มีเงื่อนไขอย่างไม่มีเงื่อนไข แต่เราต้องจับคู่ \b11+?\B ซึ่งเป็นสตริงย่อยที่เป็นไปได้ที่เล็กที่สุดที่เริ่มต้นเมื่อเริ่มต้นการทำงานมีอย่างน้อย 2 วินาทีและไม่ครอบคลุมการทำงานทั้งหมด การทำซ้ำครั้งต่อ ๆ ไปจะไม่สามารถใช้ทางเลือกนี้อีกครั้งเนื่องจาก \b ดังนั้นในการทำซ้ำทั้งหมดต่อไปเราจะจับคู่ \1 นั่นคือสตริงย่อยเดียวกันซ้ำแล้วซ้ำอีก ขั้นตอนนี้ต้องกดท้ายสตริง ( $ ) เพื่อให้แน่ใจว่าเราได้บันทึกและหารจริงแล้ว ประโยชน์ของการใช้วิธีการที่ค่อนข้างยุ่งยากนี้คือกลุ่มที่ 1 จะถูกใช้อย่าง n/d ครั้งนั่นคือสิ่งที่ยังคงอยู่หลังจากที่หารหารตัวหาร d .

เราแทนที่การจับคู่นี้ด้วย d ( $1 ) การแยก ; และ n/d ( $#1$* ซึ่งแทรก $#1 สำเนา 1 , โดยที่ $#1 เป็นตัวเลขที่จับได้จากกลุ่ม 1 )

กระบวนการนี้จะหยุดเมื่อการรันขั้นสุดท้ายในสตริงเป็นตัวหลักเพราะ regex ไม่ตรงกับอีกต่อไป

; 

ทั้งหมดที่เราต้องทำเพื่อรวมจำนวนครั้งคือการลบตัวคั่นทั้งหมด


ovs 10/04/2017.

Python 2 , 84 bytes

 f=lambda n,d=2:n>1and(n%d and f(n,d+1)or d+f(n/d))
i=input()
exec'i=f(i);'*i
print i 

ทดลองใช้แบบออนไลน์!

4 comments
Kevin Cruijssen 10/04/2017
นี้อาจเป็นคำถามโง่สวย แต่อย่างไร f=lambda n,d=2:n>1and(n%d and f(n,d+1)or d+f(n/d)) ทำงานอย่างไร ฉันไม่เคยเขียนโปรแกรมใน Python (Java ส่วนใหญ่และ C #) ดังนั้นฉันไม่แน่ใจว่าผลลัพธ์ของฟังก์ชันนี้คืออะไร ฟังก์ชันนี้จะแก้ไขข้อมูล n และส่งคืนหรือคล้ายกับ boolean ที่ n>1and(n%d and f(n,d+1)or d+f(n/d)) มีค่าเป็น 0 หรือ 1 หรือ 0 หรือ n หรืออย่างอื่น? ฉันพยายามที่จะเห็นภาพวิธีการพอร์ตของนี้จะมีลักษณะเช่นใน Java / C # แต่ฉันไม่สามารถเพราะฉันไม่เข้าใจจริงๆ lambdas Python เช่นนี้โดยทั่วไป
1 ovs 10/04/2017
@KevinCruijssen นี้เทียบเท่ากับ n>1 ? (n%d!=0 ? f(n, d+1) : d+f(n/d)) : n>1 n>1 ? (n%d!=0 ? f(n, d+1) : d+f(n/d)) : n>1 โดยทั่วไปข้อกำหนด x and y เทียบเท่ากับ x ? y : x x ? y : x x and y or z เท่ากับ x ? y : z x ? y : z ในกรณีส่วนใหญ่
1 ovs 10/04/2017
@KevinCruijssen พอร์ต Java จะคล้ายกับ f=(n,d=2)->n>1?n%d>0?f(n,d+1):d+f(n/d):0
Kevin Cruijssen 10/04/2017
อาโอเค. ขอบคุณสำหรับคำอธิบายตอนนี้มันทำให้รู้สึกมากขึ้น และฉันจำ x and y เป็น x ? y : x x ? y : x จาก JavaScript ด้วย ขอบคุณ!

Mego 10/04/2017.

จริงๆแล้ว 7 ไบต์

⌠w♂πΣ⌡Y 

ทดลองใช้แบบออนไลน์!

คำอธิบาย:

⌠w♂πΣ⌡Y
⌠    ⌡Y  do this until output stops changing (fixed-point combinator)
 w         factor into [prime, exponent] pairs
  ♂π       product of each pair
    Σ      sum of products 

Giuseppe 10/04/2017.

R + pracma , 53 ไบต์

 function(n){for(i in 1:n)n=sum(pracma::factors(n))
n} 

ทดลองใช้แบบออนไลน์! (R-ซอ)

R ไม่มีปัจจัยสำคัญที่สร้างขึ้น แต่แพคเกจจำนวนมาก ( pracma , numbers , ฯลฯ ) ทำดังนั้นฉันจึงเลือกสั้นสะดวก


Cinaski 10/05/2017.

Ohm v2 , 4 ไบต์

·ΘoΣ 

ทดลองใช้แบบออนไลน์!

Explanation:

·Θ    evaluate the block until the result returned has already been seen
   Σ  sum
  o   the full prime factorization 

Sherlock9 10/04/2017.

เยลลี่ 6 ไบต์

คำตอบนี้ใช้หนึ่งในวลีที่สำคัญหลายตัวของวุ้นและสามารถ repeat until the results are no longer unique

ÆfSµÐL 

Try it online!

4 comments
caird coinheringaahing 10/04/2017
ฉันคิดว่า คุณก้าวออกไป แต่เมื่อพิจารณาแนวทางของคุณฉันไม่แน่ใจว่าคำตอบนั้นใช้ได้หรือไม่
Sherlock9 10/04/2017
@ cairdcoinheringaahing ฉันได้ตรวจสอบคำตอบของเขา (หรือมากกว่าเทียบเท่าหลาม) ตั้งแต่ 1 ถึง 100000 และทำงาน. ฉันคิดว่า 1 เป็นกรณีเดียวที่จำนวนขั้นตอนที่จำเป็นเท่ากับ n (ซึ่งเป็นค่าปรับกับ 1 เราจะต้องใช้เพียงครั้งเดียว) และมีไม่ดูเหมือนจะเป็นกรณีใด ๆ ที่จำนวนขั้นตอนมากขึ้น กว่า n (เช่นมีดูเหมือนจะไม่ counterexamples ใด ๆ ) อืมฉันได้รับ outgolfed: D
caird coinheringaahing 10/04/2017
ดีมันเกิดขึ้น แม้ว่า +1 จะเป็นโค้ดเดียวกับที่ฉันคิดถึงเมื่อดูความท้าทายนี้
Chris 10/05/2017
ผลรวมของปัจจัยสำคัญของ n จะน้อยกว่าหรือเท่ากับ n ซึ่งทำให้ง่ายต่อการพิสูจน์ว่า n อยู่เสมอเกินพอ

Luis Mendo 10/04/2017.

MATL , 6 ไบต์

ใช้ ความคิดของ scottinet ใน การวนรอบเวลามากกว่าที่ต้องการ ขอบคุณที่ ปุย เพื่อชี้ให้เห็นข้อผิดพลาดได้รับการแก้ไขในขณะนี้

t:"Yfs 

Try it online!

คำอธิบาย

t       % Take input (implicit). Duplicate
:"      % Do the following that many times
  Yf    %   Array of prime factors
  s     %   Sum of array
        % End (implicit). Display (implicit) 
3 comments
Shaggy 10/04/2017
นี้ดูเหมือนจะล้มเหลวสำหรับ 4
Luis Mendo 10/04/2017
@Shaggy ขอบคุณ! การทำงานที่นั่น
Luis Mendo 10/04/2017
@Shaggy แก้ไขแล้ว

AdmBorkBork 10/04/2017.

PowerShell ขนาด 124 ไบต์

 function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
for($x=$args[0];$l-ne$x){$l=$x;$x=(f($x))-join'+'|iex}$x 

ทดลองใช้แบบออนไลน์!

PowerShell ไม่มีตัวประกอบที่สำคัญตัวใดตัวหนึ่งดังนั้นโค้ดนี้จึงใช้รหัสจากคำตอบของฉันเกี่ยวกับ Buddies หลักที่สำคัญ (บรรทัดด้านบน) เพื่อทำการคำนวณแบบจําลอง

บรรทัดที่สองคือเนื้อของโปรแกรมนี้ เรานำเข้าจาก $args เป็น $x แล้ว for loop จนถึง $l คือ -n ot e qual ถึง $x (การทำซ้ำครั้งแรก $l เป็น $null และ $x เป็นจำนวนเต็มดังนั้นเราจะวนอย่างน้อยหนึ่งครั้ง)

ภายในลูปเราตั้งค่า $l = $x เพื่อตรวจสอบว่าเราได้เข้าสู่จุดสิ้นสุดของลูปหรือไม่ จากนั้นเราจะได้รับปัจจัยของ $x กับ f($x) , -join เหล่านั้นร่วมกับ + และ |iex พวกเขา (ย่อมาจาก Invoke-Expression และคล้ายกับ eval ) ที่เก็บไว้ใน $x ดังนั้นเราจึงได้รับ "จุดสิ้นสุด" ซึ่งการรวมตัวของปัจจัยสำคัญที่รวมกันกลับคืนมาเอง จากนั้นเราก็วาง $x บนท่อและเอาท์พุทเป็นนัย


user202729 10/04/2017.

Mathematica, 35 ไบต์

#//.x_:>Tr[1##&@@@FactorInteger@x]& 

ทดลองใช้แบบออนไลน์!

(คณิตศาสตร์ไม่สนับสนุน Tr ฉันต้องใช้มันด้วยตนเอง)

5 comments
3 Martin Ender♦ 10/04/2017
1##& สั้นสำหรับ Times และ FixedPoint เกือบจะสั้นลงด้วย //. : #//.x_:>Tr[1##&@@@FactorInteger@x]&
user202729 10/04/2017
@MartinEnder ขอบคุณ! ฉันควรรู้เกี่ยวกับ Times แต่ฉันไม่รู้จักเคล็ดลับ FixedPoint
Jenny_mathy 10/04/2017
รหัสของคุณเขียนใน Mathematica นี่ไม่ใช่ฟังก์ชันคณิตศาสตร์ คุณควรเปลี่ยนชื่อภาษาเป็น Mathematica หรือ Tr to Total
user202729 10/04/2017
@ {no one} ขออภัยชื่อภาษา (คณิตศาสตร์) เป็นความผิดพลาด {i cri evritime} แก้ไขแล้ว

Snack 10/04/2017.

ทับทิม 63 ไบต์

 ->nNO 

ทดลองใช้แบบออนไลน์!

ใช้ค่าสถานะ -rprime สำหรับ +6 ไบต์เพื่อใช้ Prime # prime_division

prime_division ส่งค่าคู่ของ [prime, exponent] (ตัวอย่างเช่นสำหรับ 24 เรามีปัจจัย [2, 2, 2, 3] ดังนั้นจึงให้ [[2, 3], [3, 1]] ดังนั้นในแต่ละขั้นตอนเรา เพียงคูณสมาชิกของคู่เหล่านั้นเข้าด้วยกันและสรุปผล


Herman Lauenstein 10/04/2017.

Javascript (ES6), 63 ไบต์

 f=n=>(q=(p=(m,x)=>m 
 

Ungolfed:

 f=n=>(                  // Recursive function `f`
    p=(m,x=2)=>(        //   Recursive function `p`, used to sum prime factors
        m 

Kevin Cruijssen 10/05/2017.

Java 8, 101 ไบต์

 n->{for(int i=n;i-->0;n=f(n,2));return n;}int f(int n,int d){return n>1?n%d>0?f(n,d+1):d+f(n/d,2):0;} 

คำตอบ Python 2 ของ Port of @ovs ที่น่าตื่นตาตื่นใจ

Explanation:

ลองใช้ที่นี่

 n->{                  // Method with integer as both parameter and return-type
  for(int i=n;i-->0;  //  Loop the input amount of times
    n=f(n,2)          //   And change `n` that many times with a separate method call
  );                  //  End of loop
  return n;           //  Then return the integer `n` as result
}                     // End of method

int f(int n,int d){   // Separated method with 2 integer parameters and integer return-type
                      // (`d` is 2 when we initially call this recursive-method)
  return n>1?         //  If input `n` is larger than 1:
    n%d>0?            //   And it's not divisible by `d`:
     f(n,d+1)         //    Do a recursive-call with `n, d+1`
    :                 //   Else:
     d                //    Sum `d` with
      +f(n/d,2)       //    a recursive call with `n/d, 2`
   :                  //  Else:
    0;                //   Simply return 0
}                     // End of separated method 

Related questions

Hot questions

Language

Popular Tags