숫자의 기준을 결정하는 방법은 무엇입니까?

Question

주어진 임의의 숫자 시스템에서 정수와 그 표현. 그 목적은 넘버 시스템의 기반을 찾는 것입니다. 예를 들어, 숫자는 10이고 표현은 000010입니다. 그런 다음 밑이 10이되어야합니다. 또 다른 예 : 숫자 21 표현은 0010101이고 밑은 2입니다. 하나 더 많은 예가 있습니다 : 숫자는 6이고 표현은 10100이고 그 다음에 밑은 sqrt (2)입니다. . 누구든지 그런 문제를 해결하는 방법을 알고 있습니까?

Answer 1

이 같은 알고리즘은 기본을 발견해야하고, 적어도 정수가 아닌베이스의 선택 범위를 좁힐해야합니다

• 이 N이 정수하자 R가에서의 표현 일 신비의 기초.
• R에서 가장 큰 자릿수를 찾고 r이라고합니다.
  • 귀하의 기지가 적어도 r + 1입니다. base == (r+1, r+2, ...)를 들어
• 는 I이 I이 base이 정체 불명의 기지 다음, N에 해당 base
  • 경우 기본 해석 R을 대표 할 수 있습니다.
  • I이 N보다 작 으면 다음 기준으로 시도하십시오.
  • 이 N보다 큰 경우 기수는 base - 1과 base 사이입니다.

그것은 무차별 방법입니다,하지만 작동합니다. I이 N보다 상당히 작은 경우 base을 하나 이상 증가시켜 조금 더 빠르게 할 수도 있습니다.

특히 정수가 아닌베이스의 경우, 속도 것들을 도움이 될 그 밖의

뭔가 : 같은 여러 사람이 언급 한 기억은, 어떤 기준의 숫자는

x = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base + a[0] 

같은 다항식으로 확장 할 수 있습니다

잠재적 인 기초를 평가할 때 전체 숫자를 변환 할 필요가 없습니다. 가장 큰 용어 인 a[n]*base^n 만 변환하여 시작하십시오. 이 값이 x보다 큰 경우 사용자의 기본 크기가 너무 크다는 것을 이미 알고 있습니다. 그렇지 않으면 한 번에 하나의 용어를 추가하십시오 (최상위에서 최하위로 이동). 그렇게하면 기초가 잘못되었다는 것을 알게 된 후에도 계산 용어를 낭비하지 않아도됩니다.

잠재적 인 기반을 제거하는 또 다른 빠른 방법이 있습니다. 위의 다항식을 재 배열하고

(x - a[0]) = a[n]*base^n + a[n-1]*base^(n-1) + ... + a[2]*base^2 + a[1]*base 

또는

(x - a[0]) = (a[n]*base^(n-1) + a[n-1]*base^(n-2) + ... + a[2]*base + a[1])*base 

당신은 x 및 a[0]의 값을 알고 얻을 수있는 것을 알 (이하 "사람"숫자는 상관없이 기지를 해석 할 수 있습니다). 이것은 (x - a[0])이 base으로 균등하게 나눌 수있는 여분의 조건을 제공합니다 (모든 a[] 값은 정수이므로). (x - a[0]) % base을 계산하고 0이 아닌 결과를 얻으면 base은 올바른 기준이 될 수 없습니다.

Answer 2

이것이 효율적으로 해결되는지 확실하지 않습니다. 난 그냥 임의의 기지를 선택하려고하면 기지가 주어진 결과가 작거나, 크거나, 숫자와 같은지보십시오. 작은 경우 큰베이스를 선택하십시오. 큰 경우 작은베이스를 선택하십시오. 그렇지 않은 경우 올바른베이스를가집니다.

Answer 3

  ___ 
     \ 
number = /__ (digit[i] * base^i) 

당신은 방금 base을 찾을 수있다, 당신은 모든 digit[i]을 알고, number을 알고있다.

이 방정식을 푸는 것이 단순한 지 복잡한 지 여부는 연습 문제로 남겨 둡니다.

Answer 4

이 당신에게 출발점 제공한다 :

1 * base^4 + 2 * base^2 + 3 = 42 

이제 값을 얻을 수있는 방정식을 해결 :

이 수와 표현, 숫자 42 represenation "0010203"이됩니다에서 방정식을 만들기를 base

Answer 5

나는 모든 경우에 대해 대답을 줄 수는 없다고 생각합니다. 그리고 실제로 그렇게 생각할 이유가 있습니다! =)

베이스를 찾는 것은 Abel and Ruffini 의해 도시 된 바와 같이, 이것은 일반적으로 수행 할 수없는

a_6 b^5 + a_5 b^4 + a_4 b^3 + a_3 b^2 + a_2 b^1 + a_1 = x. 

해결 수단베이스 (B)에 표시 a_6 a_5 a_4 a_3 a_2 a_1와 숫자 X 주어. 더 짧은 숫자는 더 운이 좋을 수도 있지만 4 자리 이상이 포함되면 수식이 점점 추해집니다.

꽤 좋은 근사 알고리즘이 있습니다. here을 참조하십시오.

Answer 6

다른 기지를 시도하고 점검해야한다고 생각합니다. 능률적이기 위해서는 시작베이스가 최대치 (숫자) + 1이 될 수 있습니다. 초과 할 때까지이 값이 너무 작 으면 이진 검색을 사용하여 범위를 좁 힙니다. 이렇게하면 정상적인 상황에서 알고리즘이 O (log n)에서 실행되어야합니다.

Answer 7

다른 게시물 중 몇 개는 숫자가 나타내는 다항식의 근원을 찾아 냄으로써 해결책을 찾을 수 있다고 제안합니다. 물론 이것은 일반적으로 작동하지만 긍정적 인 정수뿐만 아니라 부정적이고 복잡한 기반을 생성하는 경향이 있습니다.

또 다른 접근법은 이것을 정수 프로그래밍 문제로 던지고 branch-and-bound를 사용하여 해결하는 것입니다.

그러나 나는 추측과 테스트의 제안이 더 비공식 제안보다 빠를 것이라고 생각합니다.

Answer 8

정수의 경우에만 그리 어렵지 않습니다 (열거 할 수 있음).

21 및 그 표현 을 살펴 보겠습니다.

1 * base^4 <= 21 < (1+1) * base^4 

는의 일부 기지의 번호를 생성하자

base low high 
2  16 32 
3  81 162 

더 일반적으로, 우리는 N가 Σ로 _내가 * 기본 I^{을 표현합니다. 최대 전력 I을 고려하는 대한 _I는 null 이외 우리는이 : 정수베이스의 경우}

a[I] * base^I <= N < (a[I] + 1) * base^I # does not matter if not representable 

# Isolate base term 
N/(a[I] + 1) < base^I <= N/a[I] 

# Ith root 
Ithroot(N/(a[I] + 1)) < base <= Ithroot(N/a[I]) 

# Or as a range 
base in ] Ithroot(N/(a[I] + 1)), Ithroot(N/a[I]) ] 

, 또는 당신이 알려진 가능한 기지의 목록이있는 경우, 나는 그들이 많은 수 있습니다 의심 가능성, 그래서 우리는 그들을 밖으로 시도 할 수 있습니다.

실제로는 Ithroot을 N/(a[I] + 1)으로 가져와 두 번째 컴퓨터를 계산하는 대신 여기에서 반복하는 것이 더 빠를 수 있습니다 (충분히 가까워 야합니다).하지만 그 직감에 대한 수학적 검토가 필요합니다.

실제로 (플로팅베이스를 찾으려고 할 때) 잘 생각해 보면 좀 더 어려울 것입니다.하지만 다음과 같은 불평등 (한두 가지 용어 포함)을 언제든지 수정할 수 있습니다. 같은 속성. 이 정수의 경우