켐프너 함수

수 이론에서, 켐프너 함수 S(n)^[1]는 주어진 양의 정수 n이 요인 s를 나누는 최소 숫자 s가 되도록 정의된다.예를 들어 숫자 8은 1!, 2!, 3!을 나누지 않고 4!를 나누기 때문에 S(8) = 4이다.

이 함수는 소수에서 선형적으로 증가하지만 요인 수에서는 하위 대수에서만 증가하는 특성을 가지고 있다.

역사

이 기능은 1883년 프랑수아 에두아르 아나톨레 루카스에 의해 처음 고려되었고,^[2] 1887년 조셉 장 침례테 뉴버그가 그 뒤를 이었다.^[3]1918년, A. J. 켐프너는 S(n)를 계산하기 위한 최초의 정확한 알고리즘을 제공했다.^[4]

켐프너 기능은 1980년 플로렌틴 스마란다체(Florentin Smarandache)가 그 기능을 재발견한 데 이어 스마란다체(Smarandache) 기능이라고도 불린다.^[5]

특성.

n은 n!을 나누기 때문에 S(n)는 항상 기껏해야 n이다.4보다 큰 n은 S(n) = n인 경우에만 소수점이다. ^[6]즉, s(n)가 n에 대해 가능한 한 큰 n이 소수점이다.다른 방향에서 S(n)가 가능한 한 작은 숫자는 모든 k ≥ 1에 대한 요인: S(k!) = k이다.

S(n)는 정수 계수를 가진 단일 다항식의 가능한 가장 작은 정도로서, 정수 위의 값은 모두 n으로 구분된다.^[1]예를 들어, S(6) = 3이라는 사실은 모든 값이 0 modulo 6인 입방 다항식이 있다는 것을 의미한다.

${\displaystyle x(x-1)(x-2)=x^{3}-3x^{2}+2x,}$

그러나 모든 2차 또는 선형 다항식(선행계수 1 포함)은 일부 정수에서 0이 아닌 모듈로 6이다.

1991년에 설정되고 1994년에 해결된 미국 수학 월간지의 진보된 문제들 중 하나에서 폴 에르드제스는 함수 S(n)가 "거의 전부" n에 대한 가장 큰 주요 요소와 일치한다고 지적했다(예외 세트의 점증적 밀도가 0이라는 의미).^[7]

계산 복잡성

임의의 숫자 n의 켐프너 함수 S(n)는 S(p^e)의 n을 나눈 소수력 p에^e 대한 최대값이다.^[4]n이 primary p일^e 때, 그것의 켐프너 함수는 p의 배수를 순차적으로 스캔하여 다항 시간 내에 충분히 p의 배수를 포함하는 요인을 찾을 수 있다.동일한 알고리즘을 요소화에서 각 주요 전력에 개별적으로 적용하고 가장 큰 값으로 이어지는 알고리즘을 선택함으로써, 이미 원시 요소화가 알려진 n에까지 확장할 수 있다.

p가 prime이고 x가 p보다 작은 n = px 형식의 숫자에 대해 n의 켐프너 함수는 p이다.^[4]이로부터 세미프라임(두 가지 프라임의 산물)의 켐프너 함수를 계산하는 것은 어려운 문제라고 여겨지는 그것의 주요 요소화를 찾아내는 것과 계산적으로 동등하다.보다 일반적으로, n이 복합수일 때마다, S(n)와 n의 가장 큰 공통점자는 반드시 n의 비교점이며, 켐프너 함수의 반복적인 평가에 의해 n이 고려될 수 있다.따라서, 켐프너 함수의 계산은 일반적으로 복합 숫자를 고려하는 것보다 쉽지 않을 수 있다.

참조 및 참고 사항

이 글에는 크리에이티브 커먼스 귀속/공유 알리케 라이센스에 따라 라이센스가 부여된 PlanetMath의 Smarandache 함수의 자료가 통합되어 있다.