A066352 -id:A066352 - cp's OEIS frontend

A200947 Sequence A007924 expressed in decimal.

0, 1, 2, 4, 5, 8, 9, 16, 17, 18, 20, 32, 33, 64, 65, 66, 68, 128, 129, 256, 257, 258, 260, 512, 513, 514, 516, 517, 520, 1024, 1025, 2048, 2049, 2050, 2052, 2053, 2056, 4096, 4097, 4098, 4100, 8192, 8193, 16384, 16385, 16386, 16388, 32768, 32769, 32770

Offset: 0

Frank M Jackson, Nov 24 2011

nonn

			8=7+1, hence A007924(8)=10001, so a(8)=17.

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - _N. J. A. Sloane_, May 20 2023]

Cf. A003714, A007895, A007924, A027941, A066352, A121559, A345297.

a:= proc(n) option remember; local m, p, r; m:=n; r:=0;
      while m>0 do
        if m=1 then r:=r+1; break fi;
        p:= prevprime(m+1); m:= m-p;
        r:= r+2^numtheory[pi](p)
      od; r
    end:
seq(a(n), n=0..52);  # Alois P. Heinz, Jun 12 2023

cprime[n_Integer] := If[n==0, 1, Prime[n]]; gentable[n_Integer] := (m=n; ptable={}; While[m != 0, (i = 0; While[cprime[i] <= m, i++]; j=0; While[j

a(n) = decimal(A007924(n)).

a(n) mod 2 = A121559(n) for n>=1. - Alois P. Heinz, Jun 12 2023

Edited by N. J. A. Sloane, May 20 2023

A007924 The number n written using the greedy algorithm in the base where the values of the places are 1 and primes.

Original entry on oeis.org

0, 1, 10, 100, 101, 1000, 1001, 10000, 10001, 10010, 10100, 100000, 100001, 1000000, 1000001, 1000010, 1000100, 10000000, 10000001, 100000000, 100000001, 100000010, 100000100, 1000000000, 1000000001, 1000000010, 1000000100, 1000000101

Offset: 0

R. Muller

Any nonnegative number can be written as a sum of distinct primes + e, where e is 0 or 1.
Terms contain only digits 0 and 1.
Without the "greedy" condition there is ambiguity - for example 5 = 3+2 has two representations.

			4 = 3 + 1, so a(4) = 101.

S. S. Pillai, "An arithmetical function concerning primes", Annamalai University Journal (1930), pp. 159-167.

John Cerkan, Table of n, a(n) for n = 0..5000
K. Kashihara, Comments and Topics on Smarandache Notions and Problems, Erhus University Press, 1996, 50 pages. See page 33.
K. Kashihara, Comments and Topics on Smarandache Notions and Problems, Erhus University Press, 1996, 50 pages. [Cached copy] See page 33.
Florian Luca & Ravindranathan Thangadurai, On an arithmetic function considered by Pillai, Journal de théorie des nombres de Bordeaux 21:3 (2009), pp. 695-701.
C. Rivera, Prime puzzle 78
F. Smarandache, Only Problems, Not Solutions!
F. Smarandache, Definitions, Solved and Unsolved Problems, Conjectures, and Theorems in Number Theory and Geometry, edited by M. Perez, Xiquan Publishing House 2000.

Cf. A200947, A066352.

Subsequence of A007088.

cprime[n_Integer] := (If[n==0, 1, Prime[n]]);gentable[n_Integer] := (m=n; ptable={};While[m!=0, (i=0; While[cprime[i]<=m, i++]; j=0;While[jFrank M Jackson, Jan 06 2012 *)

a(n)=if(n>1, my(p=precprime(n)); 10^primepi(p)+a(n-p), n) \\ Charles R Greathouse IV, Feb 01 2013

a(n) is the binary representation of b(n) = 2^pi(n) + b(n-p(pi(n))) for n > 0 and a(0) = b(0)= 0, where pi(k) = number of primes <= k (A000720) and p(k) = k-th prime (A008578). - Frank Ellermann, Dec 18 2001

Additional references from Felice Russo, Sep 14 2001
Antedated to 1930 by Charles R Greathouse IV, Aug 28 2010
Definition clarified by Frank M Jackson and N. J. A. Sloane, Dec 30 2011

A075058 Lexicographically earliest infinite sequence of distinct positive numbers with the property that every positive integer is a sum of distinct terms (see algorithm below).

Original entry on oeis.org

1, 2, 3, 7, 13, 23, 47, 97, 193, 383, 769, 1531, 3067, 6133, 12269, 24533, 49069, 98129, 196247, 392503, 785017, 1570007, 3140041, 6280067, 12560147, 25120289, 50240587, 100481167, 200962327, 401924639, 803849303, 1607698583, 3215397193, 6430794373

Offset: 0

Amarnath Murthy, Sep 07 2002

nonn

This sequence starts with a(0)=1, subsequent terms a(n) for n > 0 being obtained by selecting the greatest prime <= 1 + Sum_{i=0..n-1} a(i). This ensures that the sequence has the required property because Sum_{i=0..n-1} a(i) >= a(n) - 1, for all n >= 0 and a(0)=1, is a necessary and sufficient condition for it to hold.

			Given that the first 7 terms of the sequence are 1,2,...,23,47 then a(8)=(greatest prime) <= (1+2+...+23,47) + 1 = 97, hence a(8)=97.

Charles R Greathouse IV, Table of n, a(n) for n = 0..1000
Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - _N. J. A. Sloane_, May 20 2023]

Cf. A068524, A007924, A066352, A200947.

prevprime[n_Integer] := (j=n; While[!PrimeQ[j], j--]; j) aprime[0]=1; aprime[n_Integer] := (aprime[n] = prevprime[Sum[aprime[m], {m, 0, n - 1}] + 1]); Table[aprime[p], {p, 0, 50}]
a[0] = 1; a[n_] := a[n] = NextPrime[Sum[a[k], {k, 0, n-1}]+2, -1]; Table[a[n], {n, 0, 33}] (* Jean-François Alcover, Sep 30 2013 *)

print1(s=1);for(n=1,20,k=precprime(s+1);print1(", "k);s+=k) \\ Charles R Greathouse IV, Apr 05 2013

a(n) = (greatest prime) <= 1 + Sum_{i=0..n-1} a(i).

a(n) ~ k*2^n, with k roughly 0.748643. - Charles R Greathouse IV, Apr 05 2013

Entry revised by Frank M Jackson, Dec 03 2011

Edited by N. J. A. Sloane, May 20 2023

A072491 Define f(1) = 0. For n>=2, let f(n) = n - p where p is the largest prime <= n. a(n) = number of iterations of f to reach 0, starting from n.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 2, 1, 2, 1, 2, 2, 2, 3, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 2, 1, 2, 2, 2, 3, 2, 1, 2, 1, 2, 2, 2, 3, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 3, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 2, 1, 2, 2, 2, 3, 2, 3, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2

Offset: 0

Amarnath Murthy, Jul 14 2002

a(p)=1, a(p+1)=2 and a(p+4)=3 if p is an odd prime but p+2 and p+4 are composite.

Number of noncomposites (A008578) needed to sum to n using the greedy algorithm. - Antti Karttunen, Aug 09 2015

			a(27)=3 as f(27)=27-23=4, f(4)=4-3=1 and f(1)=0.

S. S. Pillai, "An arithmetical function concerning primes", Annamalai University Journal (1930), pp. 159-167.

Antti Karttunen, Table of n, a(n) for n = 0..10007

Cf. A008578, A072492. A066352(n) is the smallest k such that a(k)=n.

Not the same as A051034: a(122) = 3, but A051034(122) = 2.

f[1]=0; f[n_] := n-Prime[PrimePi[n]]; a[n_] := Module[{k, x}, For[k=0; x=n, x>0, k++; x=f[x], Null]; k]

a(n)=if(n<4,n>0,1+a(n-precprime(n))) \\ Charles R Greathouse IV, Feb 04 2013

On Cramér's conjecture, a(n) = O(log* n). - Charles R Greathouse IV, Feb 04 2013

Edited by Dean Hickerson, Nov 26 2002

a(0) = 0 prepended by Antti Karttunen, Aug 09 2015

A185101 The number n written using the minimum number of terms in the base where the values of the places are 1 and primes (noncomposites). For multiple solutions the smallest binary value is chosen.

Original entry on oeis.org

0, 1, 10, 100, 101, 1000, 1001, 10000, 1100, 10010, 10100, 100000, 11000, 1000000, 100100, 1000010, 101000, 10000000, 110000, 100000000, 1010000, 100000010, 10001000, 1000000000, 1100000, 1000000010, 100010000, 1100100, 10100000, 10000000000

Offset: 0

Frank M Jackson, Jan 23 2012

nonn

There are many ways of generating binary vectors a(n) for selecting noncomposites that when summed give n. A007924 uses the greedy algorithm. The above sequence uses the strong Goldbach conjecture that any integer is the sum of at most three distinct summands. It generates a(n) to select the minimum number of distinct noncomposites. Where there are multiple solutions, it chooses the smallest binary vector.

			n=57 which is > 6 and odd, so m = (nextprime > 57/3) = 23 and n-m = 34 is even, thus A082467(17) = 6 and algorithm selects {23,11,23}. These are not distinct primes, so m = nextprime(nextprime > n/3) = 29 and A082467(14)=3, thus a(n) selects {29,11,17} as the binary vector 10010100000.

Eric Weisstein's World of Mathematics, Goldbach Conjecture.

Cf. A007924, A066352, A200947.

nextprime[j_] := Module[{k}, If[j==0, 1, (k=Floor[j]+1; While[!PrimeQ[k], k++]; k)]]; primetable[n_] := Module[{p, q}, Which[n==1, {0, 2, 0}, n==2, {1, 3, 0}, n==3, {1, 5, 0}, True, (p=n+1; q=2n-p; While[q>0&&!(PrimeQ[p]&&PrimeQ[q]), p++; q--]; {0, q, p})]]; fintable[m_] := Module[{temptable}, Which[m==0, {0, 0, 0}, m==1, {1, 0, 0}, PrimeQ[m], {0, m, 0}, PrimeQ[m-2]&&m>4, {0, 2, m-2}, EvenQ[m], primetable[m/2], True, (temptable=primetable[(m-nextprime[m/3])/2]; If[temptable[[3]]==nextprime[m/3], (temptable=primetable[(m-nextprime[nextprime[m/3]])/2]; temptable[[1]]=nextprime[nextprime[m/3]]), temptable[[1]]=nextprime[m/3]]; temptable)]]; decimal[t_] := Module[{temp2table, tempdecimal=0}, (temp2table=fintable[t]; If[temp2table[[1]]==0, Null, tempdecimal=tempdecimal+2^PrimePi[temp2table[[1]]]]; If[temp2table[[2]]==0, Null, tempdecimal=tempdecimal+2^PrimePi[temp2table[[2]]]]; If[temp2table[[3]]==0, Null, tempdecimal=tempdecimal+2^PrimePi[temp2table[[3]]]];tempdecimal)];Table[IntegerString[decimal[i], 2], {i, 0, 100}]

For n, 1 to 6, a(n) is manually defined. For n prime, a(n) selects n. For n > 6 and n-2 prime, a(n) selects 2 and n-2. For n > 6 and even, use A082467(n/2) to give k, then a(n) selects n/2+k, n/2-k. For n>6 and odd, let m = (nextprime > n/3), then n-m is even and A082467((n-m)/2) gives k, a(n) selects m, (n-m)/2-k, (n-m)/2+k. If m = (n-m)/2+k, then m = nextprime(nextprime > n/3) and repeat.

Name clarified by Frank M Jackson, Oct 08 2013

A201997 a(n) is the decimal value of the binary vector used to select terms of A075058 whose sum is n.

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 32, 33, 34, 36, 37, 38, 39, 40, 41, 42, 44, 45, 46, 48, 49, 50, 52, 53, 54, 55, 56, 57, 58, 60, 64, 65, 66, 68, 69, 70, 71, 72, 73, 74, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87

Offset: 0

Frank M Jackson, Dec 07 2011

			For n=22, the binary vector when applied to A075058 is {0,1,0,1,1,0,...}, consequently 2+7+13=22. The decimal value of the binary vector (in ascending powers of 2) is 26, so a(22)=26.

Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - _N. J. A. Sloane_, May 20 2023]

Cf. A007924, A066352, A200947, A075058.

prevprime[n_Integer] := (j=n; If[n==1, 1, While[!PrimeQ[j], j--]; j]); aprime[n_Integer] := (aprime[n]=prevprime[Sum[aprime[m], {m, 0, n - 1}] + 1]); gentable[n_Integer] := (m=n; ptable={0}; While[m!=0, (i=0; While[aprime[i]<=m && ptable[[i + 1]]!=1, (AppendTo[ptable, 0];i++)]; ptable[[i]] = 1; m = m - aprime[i - 1])]; ptable); decimal[n_Integer] := (gentable[n]; Sum[2^(k-1)*ptable[[k]], {k, 1, Length[ptable]}]); aprime[0]=1; Table[decimal[r], {r,0,100}]

Binary(a(n)) x A075058 = n, where x is the inner product and the binary vector is in ascending powers of 2 with infinite trailing zeros.

Edited by N. J. A. Sloane, May 20 2023

A202618 a(n) is the smallest integer that is the sum of n distinct terms of A075058.

Original entry on oeis.org

0, 1, 4, 6, 19, 42, 89, 96, 289, 672, 1441, 2972, 6039, 12172, 24441, 48974, 98043, 196172, 392419, 784922, 1569939, 3139946, 6279987, 12560054, 25120201

Offset: 0

Frank M Jackson, Dec 21 2011

Any nonnegative integer can be written as a sum of distinct terms of A075058. a(n) is the smallest integer that is the sum of n distinct terms of A075058 in the same way that A066352 gives a Pillai sequence for the sequence comprising 1 followed by all the primes.

			For n=5, the binary vector at A201997(54) is the smallest binary vector containing 5 1's and when applied to A075058 selects the integer 42. Consequently because 42=23+13+3+2+1 and 1,2,3,13,23 are all terms of the complete sequence A075058, a(5)=42.

Wikipedia, "Complete" sequence. [Wikipedia calls a sequence "complete" (sic) if every positive integer is a sum of distinct terms. This name is extremely misleading and should be avoided. - _N. J. A. Sloane_, May 20 2023]

Cf. A007924, A066352, A200947, A075058, A201997.

prevprime[n_Integer] := (j=n;If[n==1, 1, While[!PrimeQ[j], j--]; j]);aprime[n_Integer] := (aprime[n]=prevprime[Sum[aprime[m], {m, 0, n - 1}]+1]);gentable[n_Integer] := (m=n;ptable={0};While[m!=0, (i=0;While[aprime[i]<=m && ptable[[i+1]]!=1, (AppendTo[ptable, 0];i++)];ptable[[i]] = 1;m=m-aprime[i - 1])];ptable);decimal[n_Integer] := (gentable[n];Sum[2^(k-1)*ptable[[k]], {k, 1, Length[ptable]}]);ones[n_Integer] :=(gentable[n];Sum[ptable[[k]], {k, 1, Length[ptable]}]);changeones[n_Integer] := (p = 0; While[ones[p] < n, p++]; p);aprime[0]=1;Table[changeones[r], {r, 0, 20}]

Find the smallest m such that binary(A201997(m)) x {1,1,1,...} = n, where x is the inner product, {1,1,1,1,...} is an infinite binary vector of 1's and binary(A201997(m)) a binary vector with infinite trailing zeros both in ascending powers of 2. Then a(n) = binary(m) x A075058, where x is the inner product and the binary vector is in ascending powers of 2 with infinite trailing zeros.

Edited by N. J. A. Sloane, May 20 2023

A296840 The smallest positive integer whose greedy representation as a sum of 3-smooth numbers (A003586) requires n terms.

Original entry on oeis.org

1, 5, 23, 185, 1721, 15545, 277689, 5586105, 113081529, 2289863865, 46369706169, 986739675321, 26376728842425, 711906436354233, 19221208539173049, 518972365315281081, 22132599848083154505, 944314039112845753929, 40290722114409383329353

Offset: 1

David Eppstein, Dec 21 2017

nonn

			For n = 4, 185 = 162 + 18 + 4 + 1 requires four terms in its greedy representation even though it has the shorter non-greedy representation 185 = 144 + 32 + 9.

David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.

Cf. A018899 (numbers requiring n terms in non-greedy representations as sums of A003586), A006892 and A066352 (sequences describing greedy representations as sums of squares and of primes respectively).

With[{nn = 19}, Block[{s = Sort@ Flatten@ Table[2^a * 3^b, {a, 0, Log[2, #]}, {b, 0, Log[3, #/2^a]}] &[10^Floor[8 nn/5]], t}, t = Transpose@ {Most@ s, Differences@ s}; Fold[Append[#1, Function[{a, n}, Last[a] + SelectFirst[t, Last[#] > Last@ a &][[1]]][#1, #2]] &, {1}, Range[2, nn]]]] (* Michael De Vlieger, Dec 22 2017 *)

a(n) is a(n-1) plus the smallest 3-smooth number s whose next successive 3-smooth number is greater than s + a(n-1). For instance, a(3) = 23 = 5 + 18, where a(2) = 5 is the predecessor of 23 in the sequence and where the first gap bigger than 5 among the 3-smooth numbers is the one from 18 to 24.

A336825 a(n) is the smallest positive integer which is expressed by the greedy algorithm as the sum of exactly n prime-powers (including 1).

Original entry on oeis.org

1, 6, 95, 360748

Offset: 1

Jonathan Hoseana, Aug 04 2020

Analogous to A066352 with prime-powers replacing primes.

			The greedy algorithm expresses every positive integer as a sum of prime-powers (including 1) by choosing the largest possible summand at each step. Consider the following initial data of such expressions:
1 = 1,
2 = 2,
3 = 3,
4 = 4,
5 = 5,
6 = 5 + 1,
7 = 7,
8 = 7 + 1,
9 = 9,
10 = 9 + 1.
The smallest positive integer which is expressed by the greedy algorithm as the sum of exactly 1 prime-power is a(1) = 1. The smallest positive integer which is expressed by the greedy algorithm as the sum of exactly 2 prime-powers is a(2) = 6. Similarly, a(3) = 95 (95 = 89 + 5 + 1) and a(4) = 360748 (360748 = 360653 + 89 + 5 + 1).

Steven and Jonathan Hoseana, The prime-power map, arXiv:2008.01368 [math.DS], 2020.

Cf. A066352, A000961 (power of primes), A031218.

ispp(n) = isprimepower(n) || (n==1); \\ A000961
f(n) = while(!ispp(n), n--); n; \\ A031218
nbs(n) = my(nb=0); while(n, n -= f(n); nb++); nb;
a(n) = my(k=1); while (nbs(k) != n, k++); k; \\ Michel Marcus, Aug 05 2020

a(1) = 1 and, for every positive integer n, a(n+1) = a(n) + q1(n), where (q1(n), q2(n)) is the first pair of consecutive prime-powers with q2(n) - q1(n) >= a(n) + 1.

cp's OEIS Frontend

A200947 Sequence A007924 expressed in decimal.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A007924 The number n written using the greedy algorithm in the base where the values of the places are 1 and primes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A075058 Lexicographically earliest infinite sequence of distinct positive numbers with the property that every positive integer is a sum of distinct terms (see algorithm below).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A072491 Define f(1) = 0. For n>=2, let f(n) = n - p where p is the largest prime <= n. a(n) = number of iterations of f to reach 0, starting from n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A185101 The number n written using the minimum number of terms in the base where the values of the places are 1 and primes (noncomposites). For multiple solutions the smallest binary value is chosen.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A201997 a(n) is the decimal value of the binary vector used to select terms of A075058 whose sum is n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A202618 a(n) is the smallest integer that is the sum of n distinct terms of A075058.

Views

Author