(정수론/파이썬) 특정 숫자 이하 제곱수 개수 세기

# '친절한 수론 길라잡이' 연습문제 13.1.b
# "대부분의 정수는 제곱수가 아니다."라는 명제가 참임을 다음 셈 함수를 이용하여 설명하여라.
# S(x) = # {x보다 작은 제곱수}
# x가 큰 수일 때 S(x)와 근사적으로 같은 간단한 x의 함수를 찾아보아라.

# 숫자를 입력하면 그 이하에 있는 제곱수를 모두 찾아 그 갯수를 출력한다.
# 가령 16을 입력하면, 1, 4, 9, 16의 4개를 출력한다.
# S(x)에서 x에 다양한 값을 넣어봐서, 그에 따른 출력 개수와의 상관 관계를 파악한다.

# num 이하에서 제곱수를 찾아 그 개수를 출력한다.
def square_number_count(num):
  root_val = int(num ** 0.5)

  answers = []
  for i in range(1, root_val+1):
    answer = i ** 2
    answers.append((i, answer))
  return len(answers), answers


print(square_number_count(16))
print(square_number_count(25))
print(square_number_count(1000))
print()

lst_len = []
lst_x = []

# S(x)에 다양한 값을 넣어봐서, 제곱수 개수와의 대략적인 상관 관계를 찾는다.
for x in range(100, 20000, 1000):
  length, res = square_number_count(x)
  print(f"{length} / {x} = {round(length/x, 4)}")
  lst_len.append(length)
  lst_x.append(x)

'''출력
(4, [(1, 1), (2, 4), (3, 9), (4, 16)])
(5, [(1, 1), (2, 4), (3, 9), (4, 16), (5, 25)])
(31, [(1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49), (8, 64), (9, 81), (10, 100), (11, 121), (12, 144), (13, 169), (14, 196), (15, 225), (16, 256), (17, 289), (18, 324), (19, 361), (20, 400), (21, 441), (22, 484), (23, 529), (24, 576), (25, 625), (26, 676), (27, 729), (28, 784), (29, 841), (30, 900), (31, 961)])
10 / 100 = 0.1
33 / 1100 = 0.03
45 / 2100 = 0.0214
55 / 3100 = 0.0177
64 / 4100 = 0.0156
71 / 5100 = 0.0139
78 / 6100 = 0.0128
84 / 7100 = 0.0118
90 / 8100 = 0.0111
95 / 9100 = 0.0104
100 / 10100 = 0.0099
105 / 11100 = 0.0095
110 / 12100 = 0.0091
114 / 13100 = 0.0087
118 / 14100 = 0.0084
122 / 15100 = 0.0081
126 / 16100 = 0.0078
130 / 17100 = 0.0076
134 / 18100 = 0.0074
138 / 19100 = 0.0072
'''
# 제곱수의 개수 변화를 보면 처음에는 0.1이었다가 0.01을 거쳐 점차 줄어들고 있다.

import numpy as np
import matplotlib.pyplot as plt
import math

print()
val_x = []
val_count = []
for x in range(100, 20000, 1000):
  count = x/(np.log(x)**2)
  print(x,  "  ", count)
  val_x.append(x)
  val_count.append(count)


plt.plot(lst_x, lst_len)
plt.plot(val_x, val_count)
plt.show()