소수를 이진수로 바꿔 자릿수 분포 보기

소수를 십진수로 늘어놓으면 별 규칙이 안 보인다. 이진수로 바꾸면 뭔가 다르게 보일까 싶어 자릿수별로 세어봤다.

소수 구하기

def check_prime(n):
    if n in primes:
        return True

    for i in range(2, n):
        if n % i == 0:
            break
    else:
        primes.append(n)
        return True

    return False

primes = []
domain = 50000

for i in range(2, domain + 1):
    check_prime(i)

for ... else 를 썼다. 나누어떨어지는 수를 만나 break 로 빠져나가면 else 가 실행되지 않는다. 끝까지 갔다는 건 나누어떨어지는 게 없었다는 뜻이라 소수다.

두 군데가 비싸다.

for i in range(2, n) 이 n 직전까지 간다. n 의 제곱근까지만 보면 된다. 약수가 있으면 제곱근보다 작은 쪽이 반드시 하나 있기 때문이다. 5만이면 224까지만 봐도 되는데 5만까지 본다.

if n in primes 도 리스트를 처음부터 훑는다. 이미 찾은 소수 목록에서 n 을 찾는 건데, n 이 새 수라면 못 찾고 끝까지 간다. 게다가 여기서는 i 를 2부터 올려가며 부르므로 n 이 목록에 있을 일이 아예 없다. 있으나 마나 한 검사에 매번 목록 전체를 훑는다.

이진 자릿수로 묶기

b = [bin(i)[2:] for i in primes]

d = {}
for i in b:
    l = len(i)
    d[l] = d[l] + 1 if l in d else 1

bin(11) 은 '0b1011' 이라 앞의 두 글자를 떼면 '1011' 이다. 그 길이가 이진 자릿수다.

d[l] = d[l] + 1 if l in d else 1 로 없으면 1, 있으면 더하기를 한 줄로 처리했다.

결과

{2: 2, 3: 2, 4: 2, 5: 5, 6: 7, 7: 13, 8: 23, 9: 43,
 10: 75, 11: 137, 12: 255, 13: 464, 14: 872, 15: 1612, 16: 1621}

5만 이하 소수 5133개의 분포다.

자릿수가 하나 늘 때마다 개수가 대략 두 배 가까이 는다. 자릿수가 k 인 수의 개수 자체가 두 배씩 늘기 때문이다. 소수의 밀도는 오히려 줄어드는데 후보가 더 빨리 늘어서 개수로는 계속 는다.

마지막 16자리만 흐름에서 벗어난다. 15자리가 1612개고 16자리가 1621개다. 16자리는 32768부터 65535까지인데 5만에서 끊었으므로 그 구간의 일부만 세어졌다. 자료의 끝이라 그런 것이지 성질이 바뀐 게 아니다.

소수 목록을 따로 저장한 것

같은 폴더에 소수를 파일에서 읽는 코드가 따로 있다.

f = open('primes.txt', 'r')
text = f.read().replace('\n', ' ')
text = re.sub(r'\s+', ',', text)
li = [int(i) for i in text.split(',')]

primes.txt 는 소수가 자릿수를 맞춰 줄바꿈과 함께 늘어선 형태다. 줄바꿈을 공백으로 바꾸고, 연속된 공백을 쉼표 하나로 눌러서 자른다.

여기 담긴 소수는 611953까지 간다. 위의 코드로 61만까지 구하려면 오래 걸리니 어딘가에서 받아온 목록으로 보인다. 뒤에 붙은 자릿수 세는 코드는 통째로 주석 처리되어 있고 이진수를 출력하는 데서 멈춰 있다.