cp's OEIS Frontend

A212658 Number of multisets {1^k1, 2^k2, ..., n^kn}, ki >= 0, with the sum of reciprocals <= 1.

%I A212658 #46 Mar 11 2019 03:26:45
%S A212658 1,2,4,8,17,37,86,199,475,1138,2769,6748,16613,40904,101317,251401,
%T A212658 624958,1555940,3882708,9701790,24276866,60817940,152508653,382828565,
%U A212658 961859364,2418662434,6086480305,15327208770,38622901484,97384378728,245686368946,620158662562
%N A212658 Number of multisets {1^k1, 2^k2, ..., n^kn}, ki >= 0, with the sum of reciprocals <= 1.
%C A212658 The number of distinct sums of reciprocals is given by A212606.
%H A212658 Dexter Senft, <a href="/A212658/b212658.txt">Table of n, a(n) for n = 0..36</a>
%o A212658 (C#)
%o A212658 /* For n=43 or greater, the least common multiple of the numbers 1..n requires more than 64 bits to represent, and C# has no such native data type. */
%o A212658 using System;
%o A212658 using System.Collections.Generic;
%o A212658 namespace A212658 {
%o A212658    class Program {
%o A212658       static long Result;
%o A212658       static long GCD(long n, long m) {
%o A212658          long mod;
%o A212658          long j = n<m ? m : n;
%o A212658          long k = n<m ? n : m;
%o A212658          while (true) if ((mod = k%j) == 0)
%o A212658             return j; else { k=j; j=mod; }
%o A212658       }
%o A212658       static long LCM(int n) { // This produces A003418
%o A212658          return n<=1 ? 1 : LCM(n-1) / GCD(LCM(n-1), n) * n;
%o A212658       }
%o A212658       static void Main(string[] args) {
%o A212658          List<long> numbers = new List<long>();
%o A212658          for (int n=1; n<=42; n++) {
%o A212658             long lcm= LCM(n);
%o A212658             numbers.Clear();
%o A212658             Result = 0;
%o A212658             for (int i=2; i<=n; i++) numbers.Add(lcm/i);
%o A212658             Count(lcm, numbers, 0);
%o A212658             Console.Write(n.ToString() + ": " + (Result+2).ToString() + "\n");
%o A212658          }
%o A212658       }
%o A212658       static void Count(long Target, List<long> L, int At) {
%o A212658          if (At >= L.Count) return;
%o A212658          if (L[At] <= Target) {
%o A212658             Result++;
%o A212658             long AmtLeft = Target - L[At];
%o A212658             if (AmtLeft >= L[L.Count-1]) Count(AmtLeft, L, At);
%o A212658          }
%o A212658          Count(Target, L, At+1);
%o A212658          return;
%o A212658       }
%o A212658    }
%o A212658 }
%o A212658 /* _Dexter Senft_, Feb 07 2019 */
%Y A212658 Cf. A212657, A212606, A212607, A020473, A092669, A092671, A208480, A003418.
%K A212658 nonn
%O A212658 0,2
%A A212658 _Max Alekseyev_, May 23 2012
%E A212658 a(24)-a(25) from _Alois P. Heinz_, Nov 20 2017
%E A212658 a(26)-a(31) from _Dexter Senft_, Feb 07 2019