cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A003313 Length of shortest addition chain for n.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9, 8, 9, 8, 9, 8, 9, 9, 9, 7, 8, 8, 8, 8
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Equivalently, minimal number of multiplications required to compute the n-th power.

Examples

			For n < 149 and for many higher values of n, a(n) is the depth of n in a tree whose first 6 levels are shown below. The path from the root of the tree to n gives an optimal addition chain. (See Knuth, Vol. 2, Sect. 4.6.3, Fig. 14 and Ex. 5.)
                  1
                  |
                  2
                 / \
                /   \
               /     \
              /       \
             /         \
            3           4
           / \           \
          /   \           \
         /     \           \
        /       \           \
       5         6           8
      / \        |         /   \
     /   \       |        /     \
    7    10      12      9       16
   /    /  \    /  \    /  \    /  \
  14   11  20  15  24  13  17  18  32
E.g., a(15) = 5 and an optimal chain for 15 is 1, 2, 3, 6, 12, 15.
It is not possible to extend the tree to include the optimal addition chains for all n. For example, the chains for 43, 77, and 149 are incompatible. See the link to Achim Flammenkamp's web page on addition chains.

References

  • Hatem M. Bahig, Mohamed H. El-Zahar, and Ken Nakamula, Some results for some conjectures in addition chains, in Combinatorics, computability and logic, pp. 47-54, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 2001.
  • D. Bleichenbacher and A. Flammenkamp, An Efficient Algorithm for Computing Shortest Addition Chains, Preprint, 1997.
  • A. Flammenkamp, Drei Beitraege zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers, Diplomarbeit, Bielefeld 1991.
  • S. B. Gashkov and V. V. Kochergin, On addition chains of vectors, gate circuits and the complexity of computations of powers [translation of Metody Diskret. Anal. No. 52 (1992), 22-40, 119-120; 1265027], Siberian Adv. Math. 4 (1994), 1-16.
  • A. A. Gioia and M. V. Subbarao, The Scholz-Brauer problem in addition chains, II, in Proceedings of the Eighth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1978), pp. 251-274, Congress. Numer., XXII, Utilitas Math., Winnipeg, Man., 1979.
  • D. E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, 2nd ed., Fig. 14 on page 403; 3rd edition, 1998, p. 465.
  • D. E. Knuth, website, further updates to Vol. 2 of TAOCP.
  • Michael O. Rabin and Shmuel Winograd, "Fast evaluation of polynomials by rational preparation." Communications on Pure and Applied Mathematics 25.4 (1972): 433-458. See Table p. 455.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A003064, A003065, A005766, A014701, A079300, A230528.

Formula

a(n*m) <= a(n)+a(m). In particular, a(n^k) <= k * a(n). - Max Alekseyev, Jul 22 2005
For all n >= 2, a(n) <= (4/3)*floor(log_2 n) + 2. - Jonathan Vos Post, Oct 08 2008
From Achim Flammenkamp, Oct 26 2016: (Start)
a(n) <= 9/log_2(71) log_2(n), for all n.
It is conjectured by D. E. Knuth, K. Stolarsky et al. that for all n: floor(log_2(n)) + ceiling(log_2(v(n))) <= a(n). (End)
a(n) <= A014701(n). - Charles R Greathouse IV, Jan 03 2018
From Szymon Lukaszyk, Apr 05 2024: (Start)
For n = 2^s, a(n)=s;
for n = 2^s + 2^m, m in [0..s-1] (A048645), a(n)=s+1;
for n = 2^s + 3*2^m, m in [0..s-2] (A072823), a(n)=s+2;
for n = 2^s + 7*2^(s-3), s>2 (A072823), a(n)=s+2.(End)

Extensions

More terms from Jud McCranie, Nov 01 2001

A249732 Number of (not necessarily distinct) multiples of 4 on row n of Pascal's triangle.

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 1, 0, 6, 4, 3, 0, 7, 2, 3, 0, 14, 12, 11, 8, 13, 6, 7, 0, 19, 14, 11, 4, 17, 6, 7, 0, 30, 28, 27, 24, 29, 22, 23, 16, 33, 26, 23, 12, 29, 14, 15, 0, 43, 38, 35, 28, 37, 22, 23, 8, 45, 34, 27, 12, 37, 14, 15, 0, 62, 60, 59, 56, 61, 54, 55, 48, 65, 58, 55, 44, 61, 46, 47, 32
Offset: 0

Views

Author

Antti Karttunen, Nov 04 2014

Keywords

Comments

a(n) = Number of zeros on row n of A034931 (Pascal's triangle reduced modulo 4).
This should have a formula (see A048967).

Examples

			Row 9 of Pascal's triangle is: {1,9,36,84,126,126,84,36,9,1}. The terms 36 and 84 are only multiples of four, and both of them occur two times on that row, thus a(9) = 2*2 = 4.
Row 10 of Pascal's triangle is: {1,10,45,120,210,252,210,120,45,10,1}. The terms 120 (= 4*30) and 252 (= 4*63) are only multiples of four, and the former occurs twice, while the latter is alone at the center, thus a(10) = 2+1 = 3.

Links

Crossrefs

Cf. A007318, A034931, A048277, A048645, A072823, A048967, A062296, A187059, A249733.

Programs

  • PARI
    A249732(n) = { my(c=0); for(k=0,n\2,if(!(binomial(n,k)%4),c += (if(k<(n/2),2,1)))); return(c); } \\ Slow...
for(n=0, 8192, write("b249732.txt", n, " ", A249732(n)));
  • Python
    def A249732(n): return n+1-(2+((n>>1)&~n).bit_count()<>1) # Chai Wah Wu, Jul 24 2025

Formula

Other identities:
a(n) <= A048277(n) for all n.
a(n) <= A048967(n) for all n.

A266214 Numbers n that are not coprime to the numerator of zeta(2*n)/(Pi^(2*n)).

Original entry on oeis.org

14, 22, 26, 28, 30, 38, 42, 44, 46, 50, 52, 54, 56, 58, 60, 62, 70, 74, 76, 78, 82, 84, 86, 88, 90, 92, 94, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 134, 138, 140, 142, 146, 148, 150, 152, 154, 156, 158, 162, 164, 166, 168, 170
Offset: 1

Views

Author

Chris Boyd, Robert Israel, Dec 24 2015

Keywords

Comments

Equivalently, n not coprime to the numerator of 2^(2n-1)*Bernoulli(2n)/(2n)! (see Lekraj Beedassy comment in A046988).
Conjecture 1: for n>=1, a(n) is identical to 2*A072823(n+1).
Conjecture 2: The corresponding GCDs are powers of 2.
Verified for n <= 10000, e.g.,
GCD = 2 for 14, 22, 26, 28, 30, 38, 42, 44, 46, 50, 52, 54, 56, 58, ...
GCD = 4 for 60, 92, 108, 116, 120, 124, 156, 172, 180, 184, 188, ...
GCD = 8 for 248, 376, 440, 472, 488, 496, 504, 632, 696, 728, 744, ...
GCD = 16 for 1008, 1520, 1776, 1904, 1968, 2000, 2016, 2032, 2544, ...
GCD = 32 for 4064, 6112, 7136, 7648, 7904, 8032, 8096, 8128, 8160
Taking GCDs vertically, column 1 = "14, 60, 248, 1008, 4064, ..." appears to be essentially the same as A171499 and A131262; (ii) column 2 = "22, 92, 376, 1520, 6112, ..." appears to be essentially the same as A010036.
From Chris Boyd, Jan 25 2016: (Start)
Determining whether n is a term of this sequence can be approached by considering odd and even factors separately, and exploiting the fact that numerator(zeta(2n)/(Pi^(2n))) = numerator(2^(2n-2)*N_2n/(D_2n*(2n)!)), where N_2n and D_2n are odd coprime integers such that Bernoulli(2n) = N_2n/2D_2n.
Case 1: odd factors. n is a term if it has an odd prime factor p (necessarily irregular) that divides N_2n at a higher multiplicity than it divides (2n)!. No such factor p of N_2n up to 2n = 10000 is of sufficient multiplicity, and the apparent scarcity of squared and higher power factors of N_2n values (see A090997) suggests that no such p is likely to exist.
Case 2: even factors. An even n is a term if 2 divides 2^(2n-2) at a higher multiplicity than it divides (2n)!. The multiplicity of 2 in 2^(2n-2) is 2n-2, and in (2n)! is 2n minus the number of 1's in the binary expansion of 2n (see A005187). Qualifying n values are therefore those where the number of 1's in the binary expansion of 2n is greater than 2. Except for its first term, A072823 comprises integers with three or more 1-bits in their binary expansion. It follows that for m > 1, 2*A072823(m) values belong to this sequence.
In summary, this sequence is essentially a supersequence of 2*A072823. Conjectures 1 and 2 are true if there are no irregular odd primes p that divide n and the numerator of Bernoulli(2n)/(2n)!. (End)

Links

Crossrefs

Cf. A010036, A072823, A131262, A171499.

Programs

  • Maple
    select(n -> igcd(n,numer(2^(2*n-1)*bernoulli(2*n)/(2*n)!)) > 1), [$1..1000]);
  • Mathematica
    Select[Range@ 170, ! CoprimeQ[#, Numerator[Zeta[2 #]/Pi^(2 #)]] &] (* Michael De Vlieger, Dec 24 2015 *)
  • PARI
    test(n) = if(gcd(numerator(2^(2*n-1)*bernfrac(2*n)/(2*n)!),n)!=1,1,0)
for(i=1,200,if(test(i),print1(i,", ")))

A091860 a(1)=1, a(n)=sum(i=1,n-1,b(i)) where b(i)=0 if a(i) and a(n-i) are both even, b(i)=1 otherwise.

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 6, 5, 6, 6, 8, 6, 8, 8, 8, 7, 8, 8, 10, 8, 10, 10, 10, 8, 10, 10, 10, 10, 10, 10, 10, 9, 10, 10, 12, 10, 12, 12, 12, 10, 12, 12, 12, 12, 12, 12, 12, 10, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 11, 12, 12, 14, 12, 14, 14, 14, 12, 14, 14, 14, 14, 14
Offset: 1

Views

Author

Benoit Cloitre, Mar 16 2004

Keywords

Crossrefs

Cf. A018900, A072823.

Programs

  • PARI
    an[1]=1;for(n=2,100,an[n]=sum(i=1,n-1,max(a(i)%2,a(n-i)%2)))

Formula

n>1 a(2n)=a(n)+2; if n is a power of 2, a(2n+1)=1+a(2n); if n is the sum of 2 distinct power of 2, a(2n+1)=2+a(2n); a(2n+1)=a(2n) otherwise

A196990 Numbers that are not the sum of two powers of 3.

Original entry on oeis.org

1, 3, 5, 7, 8, 9, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 29, 31, 32, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76
Offset: 1

Views

Author

Jeremy Gardiner, Oct 08 2011

Keywords

Comments

Complement of A055235 (sums of two powers of 3)

Examples

			a(2)=3 because 3 cannot be expressed as the sum of two powers of 3

Crossrefs

Cf. A055235, A072823.

A372152 Number of k in the range 2^n <= k < 2^(n+1) whose shortest addition chain does not have length n, n+1 or n+2.

Original entry on oeis.org

0, 0, 0, 0, 2, 9, 30, 80, 193, 432, 925, 1928, 3953, 8024, 16189, 32544
Offset: 0

Views

Author

Szymon Lukaszyk, Apr 20 2024

Keywords

Comments

The length of the shortest addition chain for k is A003313(k).
Dividing natural numbers into sections 2^n <= k < 2^(n+1), some of the 2^n numbers available in a section have the shortest addition chains given by
n (for k=2^n),
n+1 (for k=2^n+2^m, m in [0..n-1], A048645), or
n+2 (for some k in A072823).
The sequence gives the numbers of k within each section (N_oth) that have the shortest addition chains other than n, n+1, and n+2.
In particular for 4 <= n <= 6, N_oth = 2^n - n^2 + 2 and for n >= 7, N_oth = 2^n - n^2 + 1.

Links

Crossrefs

Cf. A003313, A048645, A072823, A014701, A024012.
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.