A064535 -id:A064535 - cp's OEIS frontend

A220418 Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)x) (1 + g(2)x^2) (1 + g(3)x^3) ... and use a(n) = - g(n).

1, 1, 2, 3, 6, 8, 18, 27, 54, 84, 186, 296, 630, 1008, 2106, 3711, 7710, 12924, 27594, 48528, 97902, 173352, 364722, 647504, 1340622, 2382660, 4918482, 9052392, 18512790, 33361776, 69273666, 127198287, 258155910, 475568220, 981288906, 1814542704, 3714566310

Offset: 1

Michel Marcus, Dec 14 2012

nonn

This is the PPE (power product expansion) of A153881 (with offset 0).
When p is prime, a(p) = (2^p-2)/p (A064535).
From Petros Hadjicostas, Oct 04 2019: (Start)
This sequence appears as an example in Gingold and Knopfmacher (1995) starting at p. 1223.
In Section 3 of Gingold and Knopfmacher (1995), it is proved that, if f(z) = Product_{n >= 1} (1 + g(n))*z^n = 1/(Product_{n >= 1} (1 - h(n))*z^n), then g(2*n - 1) = h(2*n - 1) and Sum_{d|n} (1/d)*h(n/d)^d = -Sum_{d|n} (1/d)*(-g(n/d))^d. The same results were proved more than ten years later by Alkauskas (2008, 2009). [If we let a(n) = -g(n), then Alkauskas works with f(z) = Product_{n >= 1} (1 - a(n))*z^n; i.e., a(2*n - 1) = -h(2*n - 1) etc.]
The PPE of 1/(1 - x - x^2 - x^3 - x^4 - ...) is given in A290261, which is also studied in Gingold and Knopfmacher (1995, p. 1234).
(End)
The number of terms in the Zassenhaus formula exponent of order n, as computed by the algorithm by Casas, Murua & Nadinic, is equal to a(n) at least for n = 2..24. - Andrey Zabolotskiy, Apr 09 2023

Alois P. Heinz, Table of n, a(n) for n = 1..2000
Giedrius Alkauskas, One curious proof of Fermat's little theorem, arXiv:0801.0805 [math.NT], 2008.
Giedrius Alkauskas, A curious proof of Fermat's little theorem, Amer. Math. Monthly 116(4) (2009), 362-364.
Fernando Casas, Ander Murua and Mladen Nadinic, Efficient computation of the Zassenhaus formula, Computer Physics Communications, 183 (2012), 2386-2391; arXiv:1204.0389 [math-ph], 2012.
H. Gingold, H. W. Gould, and Michael E. Mays, Power Product Expansions, Utilitas Mathematica 34 (1988), 143-161.
H. Gingold and A. Knopfmacher, Analytic properties of power product expansions, Canad. J. Math. 47 (1995), 1219-1239.
W. Lang, Recurrences for the general problem.

Cf. A064535, A147541, A153881, A157162, A170908, A170909, A170910, A170911, A170912, A170913, A170914, A170915, A170916, A170917, A220420, A273866, A290261.

b:= proc(n, i) option remember; `if`(n=0 or i<1, 1,
      b(n, i-1)+a(i)*b(n-i, min(n-i, i)))
    end:
a:= proc(n) option remember; 2^n-b(n, n-1) end:
seq(a(n), n=1..40);  # Alois P. Heinz, Jun 22 2018

b[n_, i_] := b[n, i] = If[n == 0 || i < 1, 1, b[n, i - 1] + a[i]*b[n - i, Min[n - i, i]]];
a[n_] := a[n] = 2^n - b[n, n - 1] ;
Array[a, 40] (* Jean-François Alcover, Jul 09 2018, after Alois P. Heinz *)

a(m) = {default(seriesprecision, m+1); gk = vector(m); pol = 1 + sum(n=1, m, -x^n); gk[1] = polcoeff( pol, 1); for (k=2, m, pol = taylor(pol/(1+gk[k-1]*x^(k-1)), x); gk[k] = polcoeff(pol, k, x);); for (k=1, m, print1(-gk[k], ", "););}

g(1) = -1 and for k > 1, g(k) satisfies Sum_{d|k} (1/d)*(-g(k/d))^d = (2^k - 1)/k, where a(k) = -g(k). - Gevorg Hmayakyan, Jun 05 2016 [Corrected by Petros Hadjicostas, Oct 04 2019. See p. 1224 in Gingold and Knopfmacher (1995).]
From Petros Hadjicostas, Oct 04 2019: (Start)
a(2*n - 1) = A290261(2*n - 1) for n >= 1 because A290261 gives the PPE of 1/(1 - x - x^2 - x^3 - ...) = (1 - x)/(1 - 2*x).
Define (A(m,n): n,m >= 1) by A(m=1,n) = -1 for n >= 1, A(m,n) = 0 for m > n >= 1 (upper triangular), and A(m,n) = A(m-1,n) - A(m-1,m-1) * A(m,n-m+1) for n >= m >= 2. Then a(n) = A(n,n). [Theorem 3 in Gingold et al. (1988).]
(End)

Name edited by Petros Hadjicostas, Oct 04 2019

A225101 Numerator of (2^n - 2)/n.

Original entry on oeis.org

0, 1, 2, 7, 6, 31, 18, 127, 170, 511, 186, 2047, 630, 8191, 10922, 32767, 7710, 131071, 27594, 524287, 699050, 2097151, 364722, 8388607, 6710886, 33554431, 44739242, 19173961, 18512790, 536870911, 69273666, 2147483647, 2863311530, 8589934591, 34359738366, 34359738367, 3714566310

Offset: 1

Alonso del Arte, Apr 28 2013

That (2^n - 2)/n is an integer when n is prime can easily be proved as a simple consequence of Fermat's little theorem.

It was believed long ago that (2^n - 2)/n is an integer only when n = 1 or a prime. In 1819, Frédéric Sarrus found the smallest counterexample, 341; these pseudoprimes are now sometimes called "Sarrus numbers" (A001567).

			a(4) = 7 because (2^4 - 2)/4 = 7/2.
a(5) = 6 because (2^5 - 2)/5 = 6.
a(6) = 31 because (2^6 - 2)/6 = 31/3.

Alkiviadis G. Akritas, Elements of Computer Algebra With Application. New York: John Wiley & Sons (1989): 66.
George P. Loweke, The Lore of Prime Numbers. New York: Vantage Press, 1982, p. 22.

Colin Barker, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Chinese Hypothesis

Cf. A001567, A064535, A159353 (denominators).

[Numerator((2^n - 2)/n): n in  [1..60]]; // Vincenzo Librandi, Nov 09 2014

A225101:=n->numer((2^n-2)/n): seq(A225101(n), n=1..50); # Wesley Ivan Hurt, Nov 10 2014

Mathematica
```
Table[Numerator[(2^n - 2)/n], {n, 50}]
```

vector(100, n, numerator((2^n - 2)/n)) \\ Colin Barker, Nov 09 2014

A056743 a(n) = phi(2^prime(n) - 1)/prime(n); a(0) = 0 by convention.

Original entry on oeis.org

0, 1, 2, 6, 18, 176, 630, 7710, 27594, 356960, 18407808, 69273666, 3697909056, 53630700752, 204064589160, 2992477516800, 169917983040000, 9770466930024800, 37800705069076950, 2202596295934991760

Offset: 0

Robert G. Wilson v, Aug 14 2000

nonn

Cf. A000020, A064535.

with numtheory; A056743 := proc(n) phi( 2^ithprime(n) - 1 )/ithprime(n); end;

Phi( A001348) / A000040. Table[EulerPhi[(2^Prime[n] - 1)]/Prime[n], {n, 1, 25}]

A203398 T(n,k), a triangular array read by rows, is the number of classes of equivalent 2-color n-bead necklaces (turning over is not allowed) that have k necklaces.

Original entry on oeis.org

2, 2, 1, 2, 0, 2, 2, 1, 0, 3, 2, 0, 0, 0, 6, 2, 1, 2, 0, 0, 9, 2, 0, 0, 0, 0, 0, 18, 2, 1, 0, 3, 0, 0, 0, 30, 2, 0, 2, 0, 0, 0, 0, 0, 56, 2, 1, 0, 0, 6, 0, 0, 0, 0, 99, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 186, 2, 1, 2, 3, 0, 9, 0, 0, 0, 0, 0, 335

Offset: 1

Geoffrey Critzer, Jan 01 2012

Equivalently, the cyclic group of order n acts on the set of length n binary sequences. T(n,k) is the number of orbits that have k elements.

			  2
  2  1
  2  0  2
  2  1  0  3
  2  0  0  0  6
  2  1  2  0  0  9
  2  0  0  0  0  0  18
  2  1  0  3  0  0  0  30
  2  0  2  0  0  0  0  0  56
  2  1  0  0  6  0  0  0  0  99
  2  0  0  0  0  0  0  0  0  0  186
  2  1  2  3  0  9  0  0  0  0  0   335

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Frank Ruskey, Combinatorial Generation Algorithm Algorithm 4.24, p. 95.

A000031 (row sums), T(n,n) = A001037, T(n,n) = A064535 when n is prime, T(n,k) = A001037(k) when k divides n.

Cf. A203399.

Needs["Combinatorica`"];
f[list_] := Sort[NestList[RotateLeft, list, Length[list]-1]]; Flatten[Table[Distribution[Map[Length, Map[Union, Union[Map[f, Strings[{0, 1}, n]]]]], Range[n]], {n, 1, 12}]]

A214606 a(n) = gcd(n, 2^n - 2).

Original entry on oeis.org

1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 14, 29, 2, 31, 2, 3, 2, 1, 2, 37, 2, 3, 2, 41, 2, 43, 2, 15, 2, 47, 2, 7, 2, 3, 2, 53, 2, 1, 2, 3, 2, 59, 2, 61, 2, 3, 2, 5, 2, 67, 2, 3, 14, 71, 2, 73, 2, 3, 2, 1, 2, 79

Offset: 1

Alex Ratushnyak, Jul 22 2012

Greatest common divisor of n and 2^n - 2.
a(n)=n iff n=1 or n is prime or n is Fermat pseudoprime to base 2 or even pseudoprime to base 2. - Corrected by Thomas Ordowski, Jan 25 2016
Indices of 1's: A121707 preceded by 1. - False, see A267999.
Numbers n such that a(n) does not equal A020639(n) (the least prime factor of n): A146077.

			a(3) = 3 because 2^3 - 2 = 6 and gcd(3, 6) = 3.
a(4) = 2 because 2^4 - 2 = 14 and gcd(4, 14) = 2.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Cf. A000918, A064535, A121707, A020639, A146077.

import java.math.BigInteger;
public class A214606 {
  public static void main (String[] args) {
    BigInteger c1 = BigInteger.valueOf(1);
    BigInteger c2 = BigInteger.valueOf(2);
    for (int n=0; n<222; n++) {
      BigInteger bn=BigInteger.valueOf(n),pm2=c1.shiftLeft(n).subtract(c2);
      System.out.printf("%s, ", bn.gcd(pm2).toString());
    }
  }
}

[GCD(n, 2^n-2): n in [1..80]]; // Vincenzo Librandi, Jan 26 2016

seq(igcd(n, (2&^n - 2) mod n), n=1 .. 1000); # Robert Israel, Jan 26 2016

Table[GCD[n, 2^n - 2], {n, 1, 59}] (* Alonso del Arte, Jul 22 2012 *)

a(n)=gcd(n,lift(Mod(2,n)^n-2)) \\ Charles R Greathouse IV, May 29 2014

A247033 Numbers of the form (3^k - 3)/k.

Original entry on oeis.org

0, 3, 8, 48, 121, 312, 16104, 122640, 7596480, 61171656, 4093181688, 2366564736720, 19924948267224, 12169835294351280, 889585277491970400, 7633882962663652968, 565719454445904325272, 365721616371321130128240, 239498069351503974657030696, 2084811062715550992506283600

Offset: 1

Juri-Stepan Gerasimov, Sep 09 2014

nonn

Generated by k: 1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 66, 67, ...

Subsequence of A246445.

			121 is in this sequence because (3^k - 3)/k = (3^6 - 3)/6 = 121.

Cf. A000040, A005935, A064535 (with form (2^k - 2)/k), A122780 (nonprimes k in a(n)), A246445, A247307 (with form (4^k - 4)/k).

A247307 Numbers of the form (4^k - 4)/k.

Original entry on oeis.org

0, 6, 20, 63, 204, 682, 2340, 381300, 1398101, 5162220, 71582788, 1010580540, 14467258260, 3059510616420, 2573485501354569, 9938978487990060, 148764065110560900, 510526106256177860940, 117943982401427236556700, 1799331452449680632120820

Offset: 1

Juri-Stepan Gerasimov, Sep 11 2014

nonn

Subsequence of A246445.
Generated by k = 1, 2, 3, 4, 5, 6, 7, 11, 12, 13, 15, 17, 19, 23, 28, 29, 31,. ..
This set of k contains all terms of A122781 and all primes. [It contains the primes because j^p == j (mod p) for every integer j if p is prime; see e.g. the corollary 4.4 to the Lagrange theorem in Jones et al.]

			a(9) = 1398101 because (4^12 - 4)/12 = 1398101 for k = 12.

G. A. Jones and J. M. Jones, Congruences with a prime-power modulus, p 65-82 in "Elementary Number Theory", Springer Undergraduate Mathematics Series, (1988).

Cf. A020136, A064535, A122781, A246445, A247033.

lista(nn) = {for (k=1, nn, va = (4^k - 4)/k; if (type(va) == "t_INT", print1(va, ", ")););} \\ Michel Marcus, Sep 12 2014

A321214 a(n) = ((2 + sqrt(5))^p + (2 - sqrt(5))^p - 2^(p+1))/p where p = prime(n).

Original entry on oeis.org

5, 20, 260, 3460, 716100, 10877380, 2678663940, 43007216580, 11439823225220, 52423583379994820, 880012516784503300, 4260164250933079388740, 1237929447780495036788100, 21180545285375859022020420, 6239638330555928133105753860

Offset: 1

Jinyuan Wang, Oct 31 2018

nonn

This is an integer sequence. For odd primes p, (2 + sqrt(5))^p + (2 - sqrt(5))^p - 2^(p+1) = binomial(p, 2)*2^(p-1)*5 + binomial(p, 4)*2^(p-3)*5^2 + ... + binomial(p, p-1)*2^2*5^((p-1)/2), and p divides binomial(p, k) for 1 <= k <= p - 1.

For n > 1, a(n) is divisible by 20.

Jinyuan Wang, Table of n, a(n) for n = 1..250

Cf. A000040, A014448, A064535, A000032.

Table[Floor[(2+Sqrt[5])^(Prime[n]) + (2-Sqrt[5])^(Prime[n]) - 2^(Prime[n]+1)]/Prime[n], {n, 1, 10}]

a(n) = my(p=prime(n)); (floor((2*quadgen(5)+1)^p+(-2*quadgen(5)+3)^p+.) - 2^(p+1))/p; \\ Michel Marcus, Nov 04 2018

a(n) = my(p=prime(n)); (([1,1;1,0]^(3*p)*[1;2])[2,1] - 2^(p+1))/p \\ Jianing Song, Dec 22 2018

a(n) = Sum_{k=1..(p-1)/2} (binomial(p, 2*k)/p)*2^(p-2*k+1)*5^k with p = A000040(n), for n > 1.
a(n) = (A014448(prime(n)) - 4)/prime(n) - 2*A064535(n).
a(n) = (A000032(3*prime(n)) - 4)/prime(n) - 2*A064535(n). - Jianing Song, Dec 22 2018

A344360 Primes p such that (2^p - 2)/p + 1 is prime.

Original entry on oeis.org

2, 3, 5, 7, 13, 53, 67, 83, 167, 1367, 2473, 4789, 34127, 219217

Offset: 1

Jorge Coveiro, May 15 2021

a(15) > 1099997, if it exists. - Karl-Heinz Hofmann, Jul 27 2021

These are primes p such that 2^((2^p-2)/p) == 1 (mod (2^p-2)/p+1) if and only if there are no pseudoprimes of the form (2^q-2)/q+1 with q prime. - Thomas Ordowski, Aug 29 2021

			7 is a term because (2^7 - 2)/7 + 1 = 19 is prime.

Cf. A064535, A344361.

Select[Prime@ Range[10^3], PrimeQ[(2^# - 2)/# + 1] &] (* Michael De Vlieger, Oct 12 2021 *)

lista(lim)={forprime(p=1,lim,if(ispseudoprime((2^p-2)/p+1), print1(p,", ")))}

c3(p) = {s=3; for(x=1, p, s=(s^2)%((2^p-2)/p+1)); if(s==9, print1(p, ", "))} /* PRP Test */

a(14) from Karl-Heinz Hofmann, Jun 11 2021

A344361 Primes p such that (2^p-2)/p - 1 is prime.

Original entry on oeis.org

5, 7, 349, 1123, 25447

Offset: 1

Jorge Coveiro, May 15 2021

a(6) > 1199999, if it exists. - Karl-Heinz Hofmann, Jul 27 2021

			7 is a term because (2^7-2)/7 - 1 = 17 is prime.

Cf. A064535, A344360.

is(p) = isprime(p) && ispseudoprime((2^p-2)/p-1) \\ Jinyuan Wang, May 15 2021

a(5) from Hugo Pfoertner, May 17 2021

cp's OEIS Frontend

A220418 Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)*x) * (1 + g(2)*x^2) *(1 + g(3)*x^3) * ... and use a(n) = - g(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A225101 Numerator of (2^n - 2)/n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

A056743 a(n) = phi(2^prime(n) - 1)/prime(n); a(0) = 0 by convention.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

A203398 T(n,k), a triangular array read by rows, is the number of classes of equivalent 2-color n-bead necklaces (turning over is not allowed) that have k necklaces.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A214606 a(n) = gcd(n, 2^n - 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Magma

Maple

Mathematica

PARI

A247033 Numbers of the form (3^k - 3)/k.

Views

Author

Keywords

Comments

Examples

Crossrefs

A247307 Numbers of the form (4^k - 4)/k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A321214 a(n) = ((2 + sqrt(5))^p + (2 - sqrt(5))^p - 2^(p+1))/p where p = prime(n).

Views

Author

A220418 Express 1 - x - x^2 - x^3 - x^4 - ... as product (1 + g(1)x) (1 + g(2)x^2) (1 + g(3)x^3) ... and use a(n) = - g(n).