टैक्सीकैब नंबर

Question

ढूँढना पहला n टैक्सीकैब नंबर खोजें। n मान को देखते हुए। मैं पहली एन टैक्सीकैब संख्याएं खोजना चाहता हूं। एक टैक्सीकैब एक संख्या है जिसे एक से अधिक तरीकों से दो सही क्यूब्स के योग के रूप में व्यक्त किया जा सकता है।

(नोट दो संबंधित लेकिन अलग सेट 'टेक्सी संख्या' के रूप में भेजा देखते हैं कि:। sums of 2 cubes in more than 1 way, और the smallest numbers that are the sum of 2 positive integral cubes in n ways यह सवाल, पूर्व सेट के बारे में है के बाद से बाद के सेट केवल पहले है छह सदस्यों में जाना जाता है)

उदाहरण के लिए:

1^3 + 12^3 = 1729 = 9^3 + 10^3 

मैं alg का एक मोटा सिंहावलोकन चाहते हैं समस्या से संपर्क करने के तरीके के Orithm या सी स्निपेट।

The first five of these are: 

    I J  K L  Number 
--------------------------------- 
    1 12  9 10  1729  
    2 16  9 15  4104  
    2 24  18 20  13832  
    10 27  19 24  20683  
    4 32  18 30  32832  

Answer 1

मैं पता लगा जवाब इस तरह से प्राप्त किया जा सकता:

#include<stdio.h> 

int main() { 
    int n, i, count=0, j, k, int_count; 
    printf("Enter the number of values needed: "); 
    scanf("%d", &n); 
    i = 1; 
    while(count < n) { 
     int_count = 0; 
     for (j=1; j<=pow(i, 1.0/3); j++) { 
      for(k=j+1; k<=pow(i,1.0/3); k++) { 
       if(j*j*j+k*k*k == i) 
       int_count++; 
      } 
     } 
     if(int_count == 2) { 
      count++; 
      printf("\nGot %d Hardy-Ramanujan numbers %d", count, i); 
     } 
     i++; 
    } 
} 

a^3+b^3 = n के बाद से, an^(1/3) से कम होना चाहिए।

Answer 2

संपादित: जो लोग क्या आर है पता नहीं है के लिए, यहाँ एक link है।

मेरा सी थोड़ा जंगली हो रहा है ... मैं आर में एक समाधान लिखूंगा, इसे अनुकूलित करना मुश्किल नहीं होना चाहिए। समाधान आर में बहुत तेजी से चलाता है, तो यह भी तेजी से सी में

# Create an hash table of cubes from 1 to 100 

numbers <- 1:100 
cubes <- numbers^3 

# The possible pairs of numbers 
pairs <- combn(numbers, 2) 

# Now sum the cubes of the combinations 
# This takes every couple and sums the values of the cubes 
# with the appropriate index 
sums <- apply(pairs, 2, function(x){sum(cubes[x])}) 

तो होना चाहिए:

numbers हो जाएगा: 1, 2, 3, 4, ..., 98, 99, 100
cubes हो जाएगा: 1, 8, 27, 64, ..., 941192, 970299, 1000000
pairs में शामिल होंगे:

 [,1] [,2] [,3] [,4] [,5] ... [,4949] [,4950] 
[1,] 1 1 1 1 1 ...  98  99 
[2,] 2 3 4 5 6 ...  100  100 

sums होगा: 9 28 65 126 217 344 ... 1911491 1941192 1970299

एक त्वरित जांच है कि हम सही रास्ते पर हैं ...

> which(sums == 1729) 
[1] 11 765 <--- the ids of the couples summing to 1729 
> pairs[,11] 
[1] 1 12 
> pairs[,765] 
[1] 9 10 

अब, चलो लगता है जो एक ही रकम के साथ जोड़ों के हैं।

table(sums) हमें तो चलो बस लगता है जो table(sums) के तत्व हैं जाने

> 9 28 35 65 72 91 ...      1674 1729 1736  
    1 1 1 1 1 1 .... <lots of 1s here> ... 1 2 1 

की तरह एक साफ सारांश देता == 2

doubles <- which(table(sums) == 2) 

taxi.numbers <- as.integer(names(doubles)) 
[1] 1729 4104 13832 20683 32832 39312 40033 46683 64232 65728 
[11] 110656 110808 134379 149389 165464 171288 195841 216027 216125 262656 
[21] 314496 320264 327763 373464 402597 439101 443889 513000 513856 515375 
[31] 525824 558441 593047 684019 704977 805688 842751 885248 886464 920673 
[41] 955016 984067 994688 1009736 1016496 

और अंत में (दो-दर-दो पढ़ने के लिए), संबंधित पूर्णांक जोड़े

> pairs[,doubles] 
    [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] 
[1,] 1 9 2 9 2 18 10 19 4 18  2 15  9 16  3 
[2,] 12 10 16 15 24 20 27 24 32 30 34 33 34 33 36 
    [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26] [,27] [,28] [,29] 
[1,] 27 17 26 12 31  4 36  6 27 12 38  8 29 20 
[2,] 30 39 36 40 33 48 40 48 45 51 43 53 50 54 
    [,30] [,31] [,32] [,33] [,34] [,35] [,36] [,37] [,38] [,39] [,40] [,41] [,42] [,43] 
[1,] 38 17 24  9 22  3 22  5 45  8 36  4 30 18 
[2,] 48 55 54 58 57 60 59 60 50 64 60 68 66 68 
    [,44] [,45] [,46] [,47] [,48] [,49] [,50] [,51] [,52] [,53] [,54] [,55] [,56] [,57] 
[1,] 32 30 51  6 54 42 56  5 48 17 38 10 45 34 
[2,] 66 67 58 72 60 69 61 76 69 76 73 80 75 78 
    [,58] [,59] [,60] [,61] [,62] [,63] [,64] [,65] [,66] [,67] [,68] [,69] [,70] [,71] 
[1,] 52 15 54 24 62 30 57  7 63 51 64  2 41 11 
[2,] 72 80 71 80 66 81 72 84 70 82 75 89 86 93 
    [,72] [,73] [,74] [,75] [,76] [,77] [,78] [,79] [,80] [,81] [,82] [,83] [,84] [,85] 
[1,] 30 23 63  8 72 12 54 20 33 24 63 35 59 29 
[2,] 92 94 84 96 80 96 90 97 96 98 89 98 92 99 
    [,86] [,87] [,88] [,89] [,90] 
[1,] 60 50 59 47 66 
[2,] 92 96 93 97 90 

तो:

1,12 और 9,10 देना 1729
2,16 और 9,15 देना 4104
2,24 और 18,20 13832
और इतने पर देना!

Answer 3

त्वरित और अनुभवहीन एल्गोरिथ्म (अगर मैं सही ढंग से इस समस्या को समझने):

के 1 एन से सभी मूल निवासी पूर्णांक के घनों की गणना करते हैं; फिर दो cubes के सभी रकम की गणना करता है। इन रकम को त्रिकोणीय मैट्रिक्स में संग्रहीत किया जा सकता है; पूरे वर्ग मैट्रिक्स भरने से बचें। अंत में, अपने त्रिकोणीय मैट्रिक्स में गैर-अद्वितीय तत्व खोजें, ये बहुत ही एचआर संख्याएं हैं (यदि आप मुझे उन नंबरों को कॉल करने देते हैं जिन्हें हम इस तरह गणना करना चाहते हैं)। इसके अलावा, मूल सूचकांक रखते हुए सरणी को सॉर्ट करके, आप आसानी से इस तरह की संख्या के अपघटन को कम कर सकते हैं।

मेरा समाधान थोड़ा दोष है: मुझे नहीं पता कि आपके इनपुट एन के आधार पर एन को कैसे ठीक किया जाए, यह है कि कम से कम एन एचआर संख्याओं के लिए मुझे कितने क्यूब्स की गणना करना है? दिलचस्प समस्या छोड़ दी।

Answer 4

नीचे एन रामानुजन संख्याओं को मुद्रित करने के लिए बेहतर जावा कोड है क्योंकि इसमें कम समय की जटिलता भी है। क्योंकि, यह लूप के लिए केवल एक है।

import java.util.*; 
public class SolutionRamanujan 
{ 
    public static void main(String args[]) throws Exception 
    { 
     SolutionRamanujan s=new SolutionRamanujan(); 
     Scanner scan=new Scanner(System.in); 
     int n=scan.nextInt(); 
     int i=0,k=1; 
     while(i<n){ 
      if(s.checkRamanujan(k)) 
      { 
       i=i+1; 
       System.out.println(i+" th ramanujan number is "+k); 
      } 
      k++; 
     } 
     scan.close(); 
    } 
    //checking whether a number is ramanujan number 
    public boolean checkRamanujan(int a) 
    { 
     int count=0; 
     int cbrt=(int)Math.cbrt(a); 
     //numbers only below and equal to cube th root of number 
     for(int i=1;i<=cbrt;i++) 
     { 
      int difference=a-(i*i*i); 
      int a1=(int) Math.cbrt(difference);    //checking whether the difference is perfect cube 

      if(a1==Math.cbrt(difference)){ 
       count=count+1; 
      } 
      if(count>2){   //checking if two such pairs exists i.e. (a*a*a)+(b*b*b)=(c*c*c)+(d*d*d)=number 
       return true; 
      } 
     } 
     return false; 
    } 
} 

Answer 5

यह समाधान (पायथन में) नीचे एन टैक्सी कैब संख्या को नीचे के दृष्टिकोण में उत्पन्न करता है। समय जटिलता एम^2 है जहां एम उच्चतम संख्या है जो एन संख्या उत्पन्न करने के लिए जाएगी। गतिशील प्रोग्रामिंग & जानवर बल:

def generate_taxi_cab_numbers(n): 
    generated_number = 0 
    v = {} 
    c = {} 
    i = 0 
    while generated_number < n: 
     c[i] = i*i*i 
     for j in xrange(i): 
      s = c[j] + c[i] 
      if s in v: 
       generated_number = generated_number + 1 
       yield (s, (j, i), v[s]) 
      v[s] = (j,i) 
     i = i + 1 


def m(n): 
    for x in generate_taxi_cab_numbers(n): 
     print x 

Answer 6

वहाँ पायथन में समाधान लिखने के लिए दो तरीके हैं।

def ramanujanDynamicProgramming(n): 
    numbers = [] 
    Ds = dict() 

    # Init List 
    for d in xrange(0, n ** 3): 
     Ds[d] = False 

    # Fill list 
    for d in xrange(0, n): 
     Ds[d**3] = d 

    for a in xrange(0, n): 
     for b in xrange(0, n): 
      for c in xrange(0, n): 

       if a != b and a != c and b != c: 
        d = a ** 3 + b ** 3 - c ** 3 

        if a != d and b != d and c != d and d >= 0 and d < n ** 3: 
         if Ds[d] != False: 
          numbers.append((a, b, c, Ds[d])) 

     return numbers 
print "Dynamic Programming" 
print ramanujanDynamicProgramming(n) 

डीपी दृष्टिकोण केवल ओ (एन^3) लेता है।

def ramanujanBruteForce(n): 
    numbers = [] 
    for a in xrange(0, n): 
     for b in xrange(0, n): 
      for c in xrange(0, n): 
       for d in xrange(0, n): 
        if a != b and a != c and a != d and b != c and b != d and c != d: 
         if a ** 3 + b ** 3 == c ** 3 + d ** 3: 
          numbers.append((a, b, c, d)) 

     return numbers 
print "Brute Force" 
print ramanujanBruteForce(n) 

बीएफ दृष्टिकोण बीएफ ओ (एन^4) है।

Answer 7

ऊपर निखिता रेड्डी की तुलना में बेहतर एल्गोरिदम। हमें (i, j) और (j, i) दोनों को जांचना नहीं है।

यहां जावा कोड है।

import java.util.*; 

public class efficientRamanujan{ 

public static void main(String[] args) { 
    efficientRamanujan s=new efficientRamanujan(); 
     Scanner scan=new Scanner(System.in); 
     int n=scan.nextInt(); 
     int i=0,k=1; 
     while(i<n){ 
      if(s.efficientRamanujan(k)) 
     { 
      i=i+1; 
      System.out.println(i+" th ramanujan number is "+k); 
     } 
     k++; 
    } 
    scan.close(); 
    } 






public boolean efficientRamanujan(int n){ 
    int count=0; 

    int x = 1; 
    int y = (int) Math.cbrt(n); 

    while (x<y){ 

     int sum = (int) Math.pow(x,3) + (int) Math.pow(y,3); 
     if(sum<n){ 
      x = x+1; 
     }else if(sum>n){ 
      y = y-1; 
     }else{ 
      count++; 
      x = x+1; 
      y = y-1; 
    } 

    if(count>=2){ 
     return true; 
    } 
} 

return false; 
} 

    } 

संदर्भ: blog