Matthieu Pluntz - cp's OEIS frontend

A378760 Smallest sum b_1 + .. + b_k among the sequences of positive integers b_1, b_2, ..., b_k such that 1 + b_1(1 + b_2(...(1 + b_k) ... )) = n.

0, 1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 7, 6, 6, 7, 8, 7, 8, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 8, 9, 8, 8, 9, 9, 9, 10, 9, 9, 9, 10, 9, 10, 9, 9, 9, 10, 9, 10, 10, 10, 10, 11, 10, 10, 10, 10, 10, 11, 10, 11, 10, 10, 10, 11, 10, 11, 10, 10, 11, 12, 11, 12, 11, 11, 11, 12, 11, 12, 11, 11, 11, 12, 11, 12, 11, 11, 11, 12, 11, 12, 11, 11, 11, 12, 12, 13, 11, 11

Offset: 1

Matthieu Pluntz, Dec 06 2024

Among rooted trees with n vertices in which vertices at depth level i-1 all have b_i children each (generalized Bethe trees), a(n) is the smallest sum of those numbers of children.

There are A003238(n) trees of this type (and sequences of b_i).

			a(5) = 3 is reached by b_1 = 2, b_2 = 1. 5 = 1 + b_1*(1 + b_2), 3 = b_1 + b_2.

Matthieu Pluntz, Table of n, a(n) for n = 1..20000

Cf. A003238.

a:= proc(n) option remember; `if`(n=1, 0, min(
      seq((n-1)/d+a(d), d=numtheory[divisors](n-1))))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Dec 06 2024

a[n_] := a[n] = If[n == 1, 0, Min[Table[(n-1)/d + a[d], {d, Divisors[n-1]}]]];
Table[a[n], {n, 1, 100}](* Jean-François Alcover, Jan 26 2025, after Alois P. Heinz *)

a = rep(0,N)
for(n in 1:(N-1)){
  divs = numbers::divisors(n)
  a[n+1] = min(divs + a[n/divs])
}

a(1) = 0; a(n+1) = min_{k divides n} (k + a(n/k)).

A361077 a(n) = largest sqrt(2n)-smooth divisor of binomial(2n, n).

Original entry on oeis.org

1, 1, 2, 4, 2, 36, 12, 24, 18, 4, 4, 24, 4, 200, 5400, 720, 90, 540, 300, 600, 180, 120, 120, 10800, 900, 3528, 10584, 784, 280, 1680, 112, 224, 882, 2940, 2940, 504, 28, 56, 4200, 19600, 980, 158760, 7560, 75600, 113400, 5040, 35280, 211680, 44100, 1800, 648, 432, 216, 45360, 1680

Offset: 0

Matthieu Pluntz, Mar 01 2023

nonn

The highest exponent in the prime factorization of a(n) is A263922(n), for n >= 2.
a(n) is even for n >= 2.
Binomial(2*n, n)/a(n) and A263931(n)/a(n) are coprime with a(n) and squarefree. By the Erdős squarefree conjecture, proved in 1996, no a(n) with n >= 5 is squarefree.

			binomial(10, 5) = 2^2*3^2*7. 2,3 <= sqrt(10), 7 > sqrt(10) so a(5) = 2^2*3^2 = 36.

Matthieu Pluntz, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Erdős Squarefree Conjecture.

Cf. A263922, A263931.

a(n) = my(m=sqrtint(2*n), f=factor(binomial(2*n, n), m+1)); for (k=1, #f~, if (f[k,1]>m, f[k,1]=1)); factorback(f); \\ Michel Marcus, Mar 03 2023

library(primes)
n = 2*10^4
pp = generate_primes(max = sqrt(n))
npinb = list()
for(p in pp){
  np = rep(0,n)
  for(t in 1:(log(n)/log(p))) np[p*(1:(n/p))] = np[1:(n/p)] + 1 #multiplicities of prime factor p in the integers
  npinb[[as.character(p)]] = cumsum(np)[2*(1:(n/2))] - 2*cumsum(np[1:(n/2)]) #multiplicities of prime factor p in the central binomial coefficients
}
res = rep(1,n/2)
for(p in pp){
  select = p^2 <= 2*(1:(n/2))
  res[select] = res[select]*p^npinb[[as.character(p)]][select]
}
#offset of res is 1

a(n) = binomial(2*n, n) / Product(p prime | p^2 > 2*n, floor(2*n/p) is odd).

A258777 Number of points of projective spaces on finite fields.

Original entry on oeis.org

1, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 17, 18, 20, 21, 24, 26, 28, 30, 31, 32, 33, 38, 40, 42, 44, 48, 50, 54, 57, 60, 62, 63, 65, 68, 72, 73, 74, 80, 82, 84, 85, 90, 91, 98, 102, 104, 108, 110, 114, 121, 122, 126, 127, 128, 129, 132, 133, 138, 140, 150, 152, 156, 158, 164, 168, 170, 174, 180, 182, 183, 192, 194, 198, 200

Offset: 1

Matthieu Pluntz, Jun 09 2015

List of integers of form (p^(k*n) - 1)/(p^k - 1) = sigma_k(p^(n-1)) = sum of d^k over all divisors d of p^(n-1), for some prime p and some positive integers k and n. The cardinality of the field is p^k and the dimension of the space is n-1.

In other words, numbers that are a repunit in at least one base that is a prime power (A246655). - Peter Munn, Oct 21 2020

			7 = (2^(1*3) - 1)/(2^1 - 1) so 7 is in the sequence. 10 = (3^(2*2) - 1)/(3^2 - 1) so 10 is in the sequence.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Pierre-Emmanuel Caprace, Pierre de la Harpe, Groups with irreducibly unfaithful subsets for unitary representations, arXiv:1807.04992 [math.GR], 2018.
Eric Weisstein's World of Mathematics, Repunit

Union of 1, A090503 and (A246655 + 1).
Subsequence of A211347.
Cf. A001231, A246655.

max = 200; Join[{1}, Select[{#, DivisorSigma[Range[Max[1, Log[#, max] // Floor]], #]}& /@ Range[2, max], PrimePowerQ[#[[1]]]&][[All, 2]] // Flatten // Union] // Select[#, # <= max&]& (* Jean-François Alcover, Jun 24 2015 after Giovanni Resta *)

list(lim)=my(v=List([1]),t); lim\=1; if(lim<2,lim=2); for(k=1,logint(lim - 1, 2), for(n=2,logint(lim*(2^k - 1) + 1, 2)\k, forprime(p=2,, t=(p^(k*n) - 1)/(p^k - 1); if(t>lim,break); listput(v,t)))); Set(v) \\ Charles R Greathouse IV, Jun 24 2015

A242390 Lexicographically earliest nonnegative integer sequence such that for every positive integer d, the sequence a(n+d)-a(n), n>=0 is injective.

Original entry on oeis.org

0, 0, 1, 0, 3, 5, 1, 8, 0, 12, 7, 18, 1, 14, 11, 27, 31, 5, 3, 17, 42, 0, 50, 15, 35, 40, 27, 33, 1, 56, 65, 9, 79, 4, 30, 23, 60, 70, 88, 11, 106, 127, 17, 98, 41, 0, 122, 141, 9, 37, 77, 163, 119, 20, 0, 57, 182, 168, 98, 92, 202, 21, 199, 154, 6, 129, 227, 81, 2, 265

Offset: 0

Matthieu Pluntz, May 12 2014

nonn

a(0)=0; a(n)= smallest nonnegative integer which is different from a(n-d)-a(k+d)-a(k) for every k=0..n-2 and d=1..n-k-1.
lim sup a(n)*log(n)*log(log(n))/n^2 seems to be positive and finite, maybe 1/pi.
Is the sequence surjective?

			Determining a(4) : 0=a(3)+a(1)-a(0);1=a(3)+a(2)-a(1);2=a(2)+a(2)-a(0) are excluded, a(4)=3 is not.

Matthieu Pluntz, Table of n, a(n) for n = 0..2100
Matthieu Pluntz, MATLAB program

cp's OEIS Frontend

User: Matthieu Pluntz

A378760 Smallest sum b_1 + .. + b_k among the sequences of positive integers b_1, b_2, ..., b_k such that 1 + b_1*(1 + b_2*(...(1 + b_k) ... )) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

R

Formula

A361077 a(n) = largest sqrt(2*n)-smooth divisor of binomial(2*n, n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

R

Formula

A258777 Number of points of projective spaces on finite fields.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A242390 Lexicographically earliest nonnegative integer sequence such that for every positive integer d, the sequence a(n+d)-a(n), n>=0 is injective.

Views

Author

Keywords

Comments

Examples

Links

A378760 Smallest sum b_1 + .. + b_k among the sequences of positive integers b_1, b_2, ..., b_k such that 1 + b_1(1 + b_2(...(1 + b_k) ... )) = n.

A361077 a(n) = largest sqrt(2n)-smooth divisor of binomial(2n, n).