일반식을 (a*10^n+x)/(10x+b)=a/b 로 놓고 풀음. x끼리 주작약분 되는거고 n=(x의 자릿수)=[log x]+1
식 정리하면 x = ab*(10^n - 1)/(10a-b) 가 나오니 적절한 x를 찾으면 되는거였는데... 참고로 난 프로그래밍 할 줄 몰라서 엑셀로 함 ㅎ 엑셀 특성상 자릿수가 커지면 정확한 값을 못 내지만 계산기로 위 식을 돌려보면 되니까 봐주셈
저번에 분석할 때는 그냥 지나갔지만 가불가 판정 조건이 2가지가 있었음.
첫 번째는 상한판정. 위 표에서 a=6, b=1을 보면 ab=6, 10a-b=4 가 될테니 x=(3/2)*(10^n-1)이라는 결과가 나오지만, 이 경우 n=(x의 자릿수)=[log x]+1 이라는 조건을 죽어도 만족시킬 수가 없음. n에 무슨 수를 넣어도 (3/2)때문에 x의 자릿수가 n보다 커지기 때문.
따라서 ab>10a-b인 경우 올바른 x를 찾을 수 없고 이걸 대충 상한판정이라고 부르기로 했다.
두 번째는 서로소판정. 10과 서로소인 p만이 페르마의 소정리를 만족시킬 수 있음. 쉽게 말해서 999...999/p 에서 p에 2나 5가 오면 9가 몇 개가 되든 절대로 정수가 될 수 없다는 뜻. 그래서 ab/(10a-b)의 기약표현식에서 분모가 10과 서로소가 아닌 경우를 다시 제외했음. 예를 들어서 a=1, b=2일 때 ab=2, 10a-b=8이 되니까 x=(1/4)*(10^n-1)인데, 999...999/4는 절대 정수가 될 수 없으니 이 경우 역시 탈락.
그래서 이 상한판정과 서로소판정을 둘 다 통과한 경우는 x의 자릿수를 결정하면 되는데, 페르마의 소정리를 조금 응용했음. 일단 100 미만의 모든 소수에 대해 1/p값의 순환주기를 엑셀 돌려서 찾았다. 1/p나 (10^n-1)/p나 거기서 거기니까... ab/(10a-b)의 기약표현에서 분모가 소수 p면 그냥 해당 자릿수(이하 Cp)로 계산하면 되는데, 분모가 합성수일 때는 소수 p, q, r,..에 대해서 10^(LCM(Cp,Cq,Cr,...))-1≡0(mod p*q*r*...)이라고 놓으면 자릿수가 LCM(Cp,Cq,Cr,...)이 되는 것.
유일한 문제라면 분모에 p^2같이 한 소인수가 여러 번 들어가면 위 공식이 성립하지 않는다는 것 정도? 다만 a와 b가 한 자리 숫자일 때는 이런 문제를 일으킬 수 있는 p가 7밖에 없고, 이게 나오는 경우도 딱 하나뿐이었음(a=5, b=1일 때 x=(5/49)(10^n-1)이고 순환주기가 42자리)
(5 102040816326530612244897959183673469387755)/(102040816326530612244897959183673469387755 1) = 5
결론)
1. a,b가 한 자리일 때 <ax>/<xb>=a/b를 만족하는 경우는 총 55가지임
2. x의 최솟값을 찾으면 <axx>/<xxb>, <axxx/xxxb>,... 역시 성립한다.
3. x의 최솟값이 가장 큰 케이스는 6/1. (61016949152542372881355932203389830508474576271186440677966) / (10169491525423728813559322033898305084745762711864406779661)=6 으로 58자리의 거대한 자릿수를 자랑함. 분모가 1이 아닌 기약분수 중에서는 5/3(46자리), 가분수가 아닌 기약분수 중에서는 3/7(22자리)이 최장으로 보임.
https://drive.google.com/file/d/16bZl_KikYiC9Z9V-zuLjoMRRYMeK3kh2/view?usp=sharing
엑셀파일. 참고로 위에서 언급한 a=5, b=1일 때 생기는 문제가 해결 안 된 버전
