Euler Projesi 242. Soru

Tek Üçlüler

{1,2, ..., n} kümesi verildiğinde f(n, k) değerini, kümenin toplamları tek olan k-elemanlı alt kümelerinin sayısı olarak tanımlarız. Örneğin f(5,3) = 4, çünkü {1,2,3,4,5} kümesinin, tek toplama sahip dört adet 3-elemanlı alt kümesi vardır: {1,2,4}, { 1,3,5}, {2,3,4} ve {2,4,5}.

n, k ve f(n, k) değerlerinin üçü de tek olduğunda, bir [n, k, f(n, k)] tek üçlüsünü oluşturduklarını söyleriz.

n ≤ 10 için tam olarak beş adet tek üçlü vardır: [1,1, f(1,1) = 1], [5,1, f(5,1) = 3], [5,5, f(5,5) = 1], [9,1, f(9,1) = 5] ve [9,9, f(9,9) = 1].

n ≤ 10¹² için kaç tek üçlü vardır?

Cevap: 997104142249036713
C#: // Shows all values of n,k, for which X(n,k)= (n+1)! / (2(n-k)!(k-1)!) is odd. // Idea : i am not interrested in odd factors, so i just query the factors of 2 (E242_getF2) // This way i get the base results up to 65. // then search for the sum in research.att .... static void Euler242_Base() { ulong lMax = 65; ulong[] lFac = new ulong[lMax]; lFac[0] = 1; lFac[1] = 1; for (ulong i = 2; i < lMax; i++) { lFac[i] = lFac[i - 1] * E242_getF2(i); } C.WriteLine(ulong.MaxValue); C.WriteLine(lFac[lMax-1]); for (ulong n = 1; n < lMax; n+=2) { C.Write(n + ": "); for (ulong k = 1; k <= n; k += 2) { ulong lRes = lFac[n+1] / (lFac[n-k] * lFac[k-1]*2); if (lRes %2 == 1) C.Write(","+k); } C.WriteLine(); } } static ulong E242_getF2(ulong N) { ulong lRes = 1; while (N % 2 == 0) { N /= 2; lRes *= 2; } return lRes; } F#: let problem () = printfn "Problem 242:" let n = 1000000000000UL let ncandidates = n/4UL let rec pow n = function | 0 -> 1UL | k -> n * (pow n (k-1)) let rec r = function | 0UL -> 0UL | k -> let t = int (floor (System.Math.Log((float k), 2.0))) (pow 3UL t) + 2UL * (r (k-(pow 2UL t))) printfn " Solution: %A" (r ncandidates) Maple: sum[n_] := (If[n > 0, ex = Floor[Log[2, n]] - 1; If[ex > 1, s = 3^(ex - 1), s = 1]; remain = n - 2^(ex + 1); If[remain <= n/2, s = s + 2*sum[remain], s = s + sum[n/2] + 2*sum[remain]], s = 0]; s); sum[10^12] Python: def p242(k): # Next exact while k % 4 != 1: k -= 1 count = 2 t = 1 p_2 = 2 n_start = n_end = 5 while True: t += count if n_end > k: break p_2 *= 2 count *= 3 n_end += p_2 * 2 while n_end != k: if n_end > k: n_end -= p_2 t -= count/3*2 else: n_end += p_2 t += count/3 if n_end > k: count = count/3 else: count = count/3*2 p_2 /= 2 return t print p242(10**12) C++: #include <stdio .h=""> unsigned long long max=70+1; unsigned long long odd_triplets(unsigned long long x) { unsigned long long ot=x%4>0,h=1; x/=2; while ((x/=2)>0) { if (x%2) ot=2*ot+h; h*=3; } return ot; } int main() { /* only the last statement of main() is essential for solution but the other draw beautiful ascii art */ unsigned long long f[max][max],g[max][max],n,k,s,i; char sum_gerade; for (n=0;n<max c="" else="" f="" for="" g="" i-1="" i="" if="" k-1="" k="" llu="" n-k="" n="" odd_triplets="" pre="" printf="" s="" sum_gerade="" t=""> </max></stdio> <stdio .h=""><max c="" else="" f="" for="" g="" i-1="" i="" if="" k-1="" k="" llu="" n-k="" n="" odd_triplets="" pre="" printf="" s="" sum_gerade="" t="">gp: <pre>N=10^12; a(x)={if(x==0,return(0),if(x==1,return(1),if(x%2==0,return(3*a(x/2)),return(2*a((x-1)/2)+a((x+1)/2));)))} a((N-1)\4+1) </max></stdio>