태그 보관물: number-theory

number-theory

제곱 숫자 자리 밀도 연속 자릿수에서 찾은 제곱 수의 비율입니다.

자신이 발명 한 숫자의 제곱 수 자릿수 밀도 (SNDD)는 숫자의 길이에 대한 연속 자릿수에서 찾은 제곱 수의 비율입니다. 예를 들어, 169는 1, 9, 16, 169의 4 제곱수를 포함하는 3 자리 숫자이므로 제곱수 자릿수 밀도는 4/3 또는 1.33입니다. 4 자리 숫자 (1444)는 6 개의 제곱 (1, 4, 4, 4, 144, 1444)을 가지므로 6/4 또는 1.5의 비율이다. 앞의 예에서 사각형을 반복 할 수 있습니다. 또한 441은 숫자 1444 내에서 연속적으로 찾을 수 없으므로 허용되지 않습니다.

당신의 임무는 가장 높은 제곱 자릿수 밀도를 가진 숫자에 대해 주어진 범위 A-B (포함)를 검색하는 프로그램을 작성하는 것입니다. 프로그램은 다음 사양을 준수해야합니다.

  • 입력 A, B를 1에서 1,000,000,000 (10 억) 범위로 가져갑니다. 예:sndd 50 1000
  • 결과적으로 SNDD가 가장 큰 숫자를 반환하십시오. 동점 인 경우 가장 작은 숫자를 반환하십시오.
  • 0은 0, 00, 000 등의 형식으로 사각형으로 계산되지 않습니다. 0으로 시작하는 사각형 (예 : 049 또는 0049)도 마찬가지입니다.
  • 전체 숫자는 제곱 숫자 일 필요는 없습니다.

예 :

sndd 14000 15000
Output: 14441

sndd 300 500
Output: 441

보너스 : 1과 1,000,000,000 사이의 가장 큰 SNDD를 가진 숫자는 무엇입니까? 이것이 가장 큰지 또는 더 큰 범위에있을 수 있는지 증명할 수 있습니까?

현재 점수 :

  1. 루비 : 142
  2. Windows PowerShell : 153
  3. 스칼라 : 222
  4. 파이썬 : 245

이제 답변이 선택되었으므로 JavaScript로 된 (참조되지 않은) 참조 구현은 다음과 같습니다. http://jsfiddle.net/ywc25/2/

답변

루비 1.9, 142 자

$><<($*[0]..$*[1]).map{|a|n=0.0;(1..s=a.size).map{|i|n+=a.chars.each_cons(i).count{|x|x[0]>?0&&(r=x.join.to_i**0.5)==r.to_i}};[-n/s,a]}.min[1]
  • (139-> 143) : 타이의 경우 고정 출력.

답변

보너스에 대한 답변 : 1e9 미만의 숫자에 대한 최고 점수는 5 / 3 = 1.666 …이며 144411449 (및 다른 것)에 의해 생성됩니다.

그러나 숫자가 클수록 더 잘 할 수 있습니다. 일반적으로 n의 점수가 x이면 n의 두 복사본을 연결하고 동일한 점수 x를 얻을 수 있습니다. 운이 좋으며 n에 첫 번째와 마지막 숫자가 동일하면 연결에서 해당 숫자 중 하나를 삭제하고 점수를 약간 향상시킬 수 있습니다 (하나는 제곱 수의 두 배보다 작고 두 번째 숫자의 두 배보다 적음) .

n = 11449441의 점수는 1.625이며 첫 번째와 마지막 숫자는 같습니다. 이 사실을 사용하여 다음과 같은 일련의 점수를 얻습니다.

1.625 for 11449441
1.666 for 114494411449441
1.682 for 1144944114494411449441
1.690 for 11449441144944114494411449441
1.694 for 114494411449441144944114494411449441

이것은 이전 숫자보다 엄격하게 (감소하지만) 더 나은 무한한 숫자의 시퀀스를 제공하며 첫 번째 2를 제외한 숫자는 <1e9의 최고 점수보다 우수합니다.

그러나이 순서는 전체적으로 최고가 아닐 수도 있습니다. 유한 점수 (12 / 7 = 1.714)로 수렴되며 한계보다 더 나은 점수를 가진 다른 숫자가있을 수 있습니다.

편집 : 더 나은 시퀀스, 1.75로 수렴

1.600 14441
1.667 144414441
1.692 1444144414441
1.706 14441444144414441
1.714 144414441444144414441

답변

Windows PowerShell, 153 154 155 164 174

$a,$b=$args
@($a..$b|sort{-(0..($l=($s="$_").length)|%{($c=$_)..$l|%{-join$s[$c..$_]}}|?{$_[0]-48-and($x=[math]::sqrt($_))-eq[int]$x}).Count/$l},{$_})[0]

1 바이트 감소에 대한 Ventero 덕분에 나는 너무 어리석어 나 자신을 찾을 수 없었습니다.

154 바이트 버전 설명 :

$a,$b=$args   # get the two numbers. We expect only two arguments, so that
              # assignment will neither assign $null nor an array to $b.

@(   # @() here since we might iterate over a single number as well
    $a..$b |  # iterate over the range
        sort {   # sort
            (   # figure out all substrings of the number
                0..($l=($s="$_").length) | %{  # iterate to the length of the
                                               # string – this will run off
                                               # end, but that doesn't matter

                    ($c=$_)..$l | %{       # iterate from the current position
                                           # to the end

                        -join$s[$c..$_]    # grab a range of characters and
                                           # make them into a string again
                    }
                } | ?{                     # filter the list
                    $_[0]-48 -and          # must not begin with 0
                    ($x=[math]::sqrt($_))-eq[int]$x  # and the square root
                                                     # must be an integer
                }

            ).Count `  # we're only interested in the count of square numbers
            / $l       # divided by the length of the number
        },
        {-$_}  # tie-breaker
)[-1]  # select the last element which is the smallest number with the
       # largest SNDD

답변

파이썬, 245 (256)

import sys
def t(n,l):return sum(map(lambda x:int(x**0.5+0.5)**2==x,[int(n[i:j+1])for i in range(l)for j in range(i,l)if n[i]!='0']))/float(l)
print max(map(lambda x:(x,t(str(x),len(str(x)))),range(*map(int,sys.argv[1:]))),key=lambda y:y[1])[0]
  • 256 → 245 : Keith Randall 의 팁 덕분에 인수 구문 분석 코드를 정리했습니다 .

stdin명령 줄 인수와 달리 범위를 읽으면 훨씬 짧을 수 있습니다 .

편집하다:

보너스와 관련하여 내 실험은 다음을 제안합니다.

추측 1 . 모든 n ∈ ℕ 에 대해 SNDD가 가장 큰 ℕ ≤ n 의 숫자에는 숫자 1, 4 및 9 만 포함해야합니다.

추측 2. ∃ n ∈ ℕ ∀ i ∈ ℕ ≥ n : SNDD ( n ) ≥ SNDD ( i ).

증거 스케치 . 숫자가 1, 4 및 9 인 사각형 세트는 유한 한 것 같습니다 . ∎

답변

스칼라, 222

object O extends App{def q(i: Int)={val x=math.sqrt(i).toInt;x*x==i}
println((args(0).toInt to args(1).toInt).maxBy(n=>{val s=n+""
s.tails.flatMap(_.inits).filter(x=>x.size>0&&x(0)!='0'&&q(x.toInt)).size.toFloat/s.size}))}

(Scala 2.9 필요)

답변

보너스 질문 고려 : 범위를 벗어난 가장 높은 SNDD는 무한대입니다.

적어도 질문을 올바르게 읽으면 100 (10 * 10)과 같은 사각형이 계산됩니다.

숫자 275625를 고려하면 25, 625, 5625, 75625 및 275625가 모두 제곱이므로 점수는 5/6입니다.

2 개의 0을 더하면 27562500이며 10/8의 점수를줍니다. 이 시퀀스의 한계는 5 / 2 = 2.5입니다.

동일한 선을 따라 원하는 수의 작은 사각형으로 끝나는 사각형을 찾을 수 있습니다. 나는 이것을 증명할 수 있지만, 당신은 아마 아이디어를 얻을 것입니다.

분명히 이것은 좋은 해결책은 아니지만 SNDD에 대한 상한이 없다는 것을 증명합니다.

답변

클로저-185 자

아마 더 최적화 될 수 있지만 여기에 간다 :

(fn[A,B]((first(sort(for[r[range]n(r A(inc B))s[(str n)]l[(count s)]][(/(count(filter #(=(int%)(max 1%))(for[b(r(inc l))a(r b)](Math/sqrt(Integer/parseInt(subs s a b))))))(- l))n])))1))

두 개의 매개 변수가있는 함수로 사용됩니다.

(crazy-function-as-above 14000 15000)
=> 14441