정수 복잡성

Integer complexity

수 이론에서 정수의 정수 복잡성은 정수의 하나와 임의의 추가, 곱, 괄호를 사용하여 정수를 나타내는 데 사용할 수 있는 가장 작은 수이다.그것은 항상 주어진 정수의 로그의 일정한 요인 안에 있다.

예

예를 들어 숫자 11은 다음과 같은 8개의 숫자를 사용하여 나타낼 수 있다.

11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1.

그러나 7개 이하를 사용한 대표성은 없다.그러므로 그것의 복잡성은 8이다.

숫자 1, 2, 3, ...의 복잡성은 다음과 같다.

1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 8, 8, 8, 8, 8, 9, 8, ... (OEIS에서 연속 A005245)

1, 2, 3, ...의 복잡성이 가장 작은 숫자는 다음과 같다.

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ...(OEIS에서 연속 A005520)

상한 및 하한

정수를 이렇게 표현하는 문제는 원래 말러&팝켄(1953)이 고려했다.그들은 주어진 복잡성 k를 가진 가장 큰 숫자를 요구했고,[1] 나중에 셀리지가 이 숫자라는 것을 보여주었다.

예를 들어 k = 10, x = 2일 때 10을 사용하여 표현할 수 있는 가장 큰 정수는22 2 3 = 36이다.그 표현은

(1 + 1) × (1 + 1) × (1 + 1 + 1) × (1 + 1 + 1).

따라서 정수 n의 복잡성은 최소 3 로그3 n이다.n의 복잡도는 최대 3 log2 n(약 4.755 log3 n)이다. n에 대한 이 길이의 표현은 호너의 방법을 n의 이진 표현에 적용하면 찾을 수 있다.[2]거의 모든 정수는 길이가 3.529 log3 n이라는 더 작은 상수 인자를 가진 로그에 의해 제한되는 표현을 가지고 있다.[3]

알고리즘 및 counterexample

일부 임계값 N까지의 모든 정수의 복잡도는 총 시간 O(N1.222911236)로 계산할 수 있다.[4]

정수 복잡성을 계산하는 알고리즘은 복잡성에 대한 몇 가지 추측을 반증하기 위해 사용되어 왔다.특히 n을 n에서 빼거나 n을 두 개의 작은 요인의 곱으로 표현하여 n의 최적 식을 얻는 경우가 반드시 있는 것은 아니다.최적 식이 이 형식이 아닌 숫자의 가장 작은 예는 353942783이다.그것은 주요한 숫자여서, 리차드 K에 대한 추측도 반증한다. 모든 소수 p의 복잡성이 1에 p - 1의 복잡성을 더한 남자.[5]실제로 = - 1= = 을 보여줄 수 있다게다가 베네치아 왕(王)은 몇 가지 흥미로운 예를 들 수 있다.예: = = = = = ×3 = = }= 5= = 5 = 2= = 2= 2 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = 23 = = 23 = 22[6]

참조

  1. ^ Mahler, K.; Popken, J. (1953), "On a maximum problem in arithmetic", Nieuw Archief voor Wiskunde, 1: 1–15, MR 0053986.
  2. ^ Guy, Richard K. (1986), "Some suspiciously simple sequences", Unsolved Problems, American Mathematical Monthly, 93 (3): 186–190, doi:10.2307/2323338, MR 1540817.
  3. ^ Shriver, Christopher E. (2015), Applications of Markov chain analysis to integer complexity, arXiv:1511.07842, Bibcode:2015arXiv151107842S.
  4. ^ Cordwell, K.; Epstein, A.; Hemmady, A.; Miller, S.; Palsson, E.; Sharma, A.; Steinerberger, S.; Vu, Y. (2017), On algorithms to calculate integer complexity, arXiv:1706.08424, Bibcode:2017arXiv170608424C
  5. ^ Fuller, Martin N. (February 1, 2008), Program to calculate A005245, A005520, A005421, OEIS, retrieved 2015-12-13.
  6. ^ Wang, Venecia (October 2012), A counterexample to the prime conjecture of expressing numbers using just ones, JNT, doi:10.1016/j.jnt.2012.08.003.

외부 링크