골프 스크립트, 68 67 62 61 문자

[.]({[.2@{1$1$%{)}{\1$/1$}if}*;;].,*0+{+}*.2$?@@.@+\@)!}do;,(

이것은 표현식입니다. n스택에 걸리고 결과는 스택에 남습니다. nstdin에서 가져 와서 결과를 stdout으로 인쇄 하는 프로그램으로 바꾸려면 선행 [을~

그것의 핵심은 [.2@{1$1$%{)}{\1$/1$}if}*;;](28 자) 스택에서 최상위 숫자를 취하고 (매우 비효율적 인 알고리즘으로) 주요 요소 목록을 생성합니다. C 스타일 유사 코드 :

ps = [], p = 2;
for (int i = 0; i < n; i++) {
    if (n % p == 0) {
        ps += p;
        n /= p;
    }
    else p++;
}

0+직전는 {+}*특별한 경우를 처리하는 것입니다 n==1Golfscript가 빈리스트를 이항 연산을 접는처럼하지 않기 때문에.

비 프라임 수정 점 중 하나는 27입니다. 나는 a == p ^{(a-1) / 2} 인 경우 고정 점 인 매핑 (p ^a -> a ² p) 을 고려하고 프로그램을 사용하지 않고 프로그램을 사용하지 않고 이것을 찾았습니다 . ( 소수의 고정 점을 제공합니다).aa==1

프로그램을 검색하면 두 번째 수정 점이 나타납니다. 30 = (2 + 3 + 5) * 3

부록 : 프라임이 아닌 두 개의 고정 점이 있다는 증거

표기법 : sopfr(x)의 주요 요인 x과 반복 의 합입니다 (A001414). (A001222) Omega(x)의 소인수 x입니다. Higley의 후속 기능은h(x) = sopfr(x) Omega(x)

우리가 fixpoint 있다고 가정 N = h(N)의 제품입니다 n=Omega(N)소수를.

N = p_0 ... p_{n-1} = h(N) = n (p_0 + ... + p_{n-1})

기본 수 이론 :로 n나눕니다 p_0 ... p_{n-1}. 그래서 w=Omega(n)소수는의 주요 요소입니다 n. Wlog 우리는 그들을 마지막으로 가져갈 것 w입니다. 우리는에 의해 양쪽을 나눌 수 있도록 nGET 및

p_0 ... p_{n-w-1} = p_0 + ... + p_{n-1}

또는

p_0 ... p_{n-w-1} = p_0 + ... + p_{n-w-1} + sopfr(n)

모든 소수 가 1보다 크면 , 소수 p_0를 p_{n-w-1}늘리면 LHS보다 LHS가 증가합니다. 따라서 주어진 n후보에 대해 모든 후보 솔루션을 열거 할 수 있습니다.

특히, LHS가 RHS보다 큰 경우 솔루션이 없을 수 있습니다. 모든 “무료”프라임을 2로 설정하십시오. 즉, 다음과 같은 경우 솔루션이 없습니다.

2^{n-w} > 2 (n-w) + sopfr(n)

sopfr(n) <= n(n = 4 또는 n 소수에만 동등 함) 때문에 다음 과 같은 경우 수정 점이 없다는 약한 진술을 할 수 있습니다

2^{n-w} > 3 n - 2 w

지주는 w우리가 다른 값을 선택할 수있는 고정 n만족을 w=Omega(n). 가장 작은 n것은 2^w입니다. 경우에하는 것으로 2^{n-w}적어도 3 (즉, 경우에 n-w>1사실 인 경우 n>2)를 증가 n누른 상태에서 w일정하게하는 것이 더 RHS보다 LHS 증가합니다. 또한 w>2가능한 n한 불평등을 최소화 하고 불평등을 충족 시키며 고정 점이 없습니다.

그것은 우리에게 세 가지 경우를 남긴다 : w = 0그리고 n = 1; w = 1그리고 n프라임; 또는 w = 2과 n반 프라임입니다.

케이스 w = 0. n = 1따라서 N모든 소수입니다.

케이스 w = 1. 경우 n = 2다음 N = 2p우리가 필요로하고 p = p + 2, 어떤 어떤 솔루션이 없습니다. 경우 n = 3우리는이 pq = p + q + 3두 솔루션 (p=2, q=5)및 (p=3, q=3). 경우 n = 5다음 2^4 > 3 * 5 - 2 * 1, 그래서 더 이상의 솔루션이 없습니다 w = 1.

케이스 w = 2. 만약 n = 4다음 N = 4pq우리가 필요 pq = p + q + 4. 여기에는 정수 솔루션 p=2, q=6이 있지만 주요 솔루션은 없습니다. 경우 n = 6다음 2^4 > 3 * 6 - 2 * 2, 그래서 더 이상의 솔루션이 없습니다 w = 2.

모든 경우가 소진되었으므로 비 프라임 고정 지점은 27과 30뿐입니다.

답변

f=->i{r=[i];(x=s=0;(2..i).map{|j|(s+=j;x+=1;i/=j)while i%j<1};r<<i=s*x)until r.uniq!;r.size}

(1..10).map &f
=> [2, 1, 1, 10, 1, 11, 1, 9, 5, 10]

l=[input('')];while size_equal(unique(l),l);n=factor(l(1));l=[sum(n)*length(n) l];endwhile;disp(length(l)-1);

i`vt0)Yftnws*yy-]xn