Qing-Hu Hou - cp's OEIS frontend

User: Qing-Hu Hou

Qing-Hu Hou has authored 3 sequences.

A320159 Number of positive integers x < prime(n)/2 such that (x^2 mod prime(n)) > (4*x^2 mod prime(n)).

0, 0, 1, 2, 2, 3, 4, 5, 4, 7, 9, 9, 10, 11, 9, 13, 13, 15, 17, 14, 18, 22, 19, 22, 24, 25, 28, 25, 27, 28, 34, 30, 34, 36, 37, 41, 39, 41, 36, 43, 42, 45, 41, 48, 49, 54, 54, 59, 54, 57, 58, 52, 60, 59, 64, 59, 67, 73, 69, 70, 72, 73, 78, 68, 78, 79, 84, 84, 84, 87, 88, 80, 96, 93, 96, 87, 97, 99, 100, 102

Offset: 1

Qing-Hu Hou and Zhi-Wei Sun, Oct 06 2018

nonn

Conjecture: Let p > 3 be a prime and let b be any integer. For a = 2,...,p-1 let I(a,b) denote the number of positive integers x < p/2 with (x^2+b mod p) > (a*x^2+b mod p). Then both S = {I(a,b): 1 < a < p and (a/p) = 1} and T = {I(a,b): 1 < a < p and (a/p) = -1} have cardinality 1 or 2 according as p is congruent to 1 or 3 modulo 4, where (a/p) is the Legendre symbol. Moreover, the set S deos not depend on the value of b.
For any prime p == 1 (mod 4), we have q^2 == -1 (mod p) for some integer q, hence ((q*x)^2 mod p) > (a*(q*x)^2 mod p) if and only if (x^2 mod p) < (a*x^2 mod p). Thus, for each a = 2,...,p-1 there are exactly (p-1)/4 positive integers x < p/2 such that (x^2 mod p) > (a*x^2 mod p). Thus I(a,0) = (p-1)/4 for all a = 2,...,p-1.
The conjecture was confirmed by Q.-H. Hou, H. Pan and Z.-W. Sun in 2021. - Zhi-Wei Sun, Jul 22 2021

			a(3) = 1 since prime(3) = 5,  (1^2 mod 5) < (4*1^2 mod 5) and (2^2 mod 5) > (4*2^2 mod 5).
a(4) = 2 since prime(4) = 7, (1^2 mod 7) < (4*1^2 mod 7), (2^2 mod 7) > (4*2^2 mod 7) and (3^2 mod 7) > (4*3^2 mod 7).

Qing-Hu Hou and Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Qing-Hu Hou, Hao Pan and Zhi-Wei Sun, A new theorem on quadratic residues modulo primes, arXiv:2107.08984 [math.NT], 2021.
Zhi-Wei Sun, Quadratic residues and related permutations, arXiv:1809.7766 [math.NT], 2018.

Cf. A000040, A000290, A319311.

Inv[p_]:=Inv[p]=Sum[Boole[Mod[x^2,p]>Mod[4x^2,p]],{x,1,(p-1)/2}];Table[Inv[Prime[n]],{n,1,80}]

a(n) = my(p=prime(n), m=p\2); if (n==1, m--); sum(k=1, m, lift(Mod(k, p)^2) > lift(Mod(2*k, p)^2)); \\ Michel Marcus, Oct 07 2018

A154404 Number of ways to express n as the sum of an odd prime, a positive Fibonacci number and a Catalan number.

Original entry on oeis.org

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

Offset: 1

Qing-Hu Hou (hou(AT)nankai.edu.cn), Jan 09 2009, Jan 18 2009

Motivated by Zhi-Wei Sun's conjecture that each integer n>4 can be expressed as the sum of an odd prime, an odd Fibonacci number and a positive Fibonacci number (cf. A154257), during their visit to Nanjing Univ. Qing-Hu Hou (Nankai Univ.) and Jiang Zeng (Univ. of Lyon-I) conjectured on Jan 09 2009 that a(n)>0 for every n=5,6,.... and verified this up to 5*10^8. D. S. McNeil has verified the conjecture up to 5*10^13 and Hou and Zeng have offered prizes for settling their conjecture (see Sun 2009).

			For n=7 the a(7)=3 solutions are 3+2+2, 3+3+1, 5+1+1.

R. Crocker, On a sum of a prime and two powers of two, Pacific J. Math. 36(1971), 103-107.
R. P. Stanley, Enumerative Combinatorics, Vol. II, Cambridge Univ. Press, 1999, Chapter 6.

Jon E. Schoenfield, Table of n, a(n) for n = 1..100000
D. S. McNeil, Sun's strong conjecture
Zhi-Wei Sun, A promising conjecture: n=p+F_s+F_t
Zhi-Wei Sun, A summary concerning my conjecture n=p+F_s+F_t (II)
Z.-W. Sun and R. Tauraso, Congruences involving Catalan numbers, arXiv:0709.1665v5.
Zhi-Wei Sun, Mixed sums of primes and other terms, preprint, 2009

Cf. A000040, A000045, A000108, A154257, A154290, A154285, A154952, A156695.

Cata:=proc(n) binomial(2*n,n)/(n+1); end proc: Fibo:=proc(n) if n=1 then return(1); elif n=2 then return(2); else return(Fibo(n-1) + Fibo(n-2)); fi; end proc: for n from 1 to 10^3 do rep_num:=0; for i from 1 while Fibo(i) < n do for j from 1 while Fibo(i)+Cata(j) < n do p:=n-Fibo(i)-Cata(j); if (p>2) and isprime(p) then rep_num:=rep_num+1; fi; od; od; printf("%d %d\n", n, rep_num); od:

a[n_] := (pp = {}; p = 2; While[ Prime[p] < n, AppendTo[pp, Prime[p++]] ]; ff = {}; f = 2; While[ Fibonacci[f] < n, AppendTo[ff, Fibonacci[f++]]]; cc = {}; c = 1; While[ CatalanNumber[c] < n, AppendTo[cc, CatalanNumber[c++]]]; Count[Outer[Plus, pp, ff, cc], n, 3]); Table[a[n], {n, 1, 88}] (* Jean-François Alcover, Nov 22 2011 *)

a(n)=my(i=1,j,f,c,t,s);while((f=fibonacci(i++))Charles R Greathouse IV, Nov 22 2011

a(n) = |{: p+F_s+C_t=n with p an odd prime and s>1}|.

More terms from Jon E. Schoenfield, Jan 17 2009
Added the new verification record and Hou and Zeng's prize for settling the conjecture. Edited by Zhi-Wei Sun, Feb 01 2009
Comment edited by Charles R Greathouse IV, Oct 28 2009

A057500 Number of connected labeled graphs with n edges and n nodes.

Original entry on oeis.org

0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840, 25201854045, 787368574080, 26667815195274, 973672928417280, 38132879409281475, 1594927540549217280, 70964911709203684440, 3347306760024413356032, 166855112441313024389625, 8765006377126199463936000

Offset: 1

Qing-Hu Hou and David C. Torney (dct(AT)lanl.gov), Sep 01 2000

Equivalently, number of connected unicyclic (i.e., containing one cycle) graphs on n labeled nodes. - Vladeta Jovovic, Oct 26 2004

a(n) is the number of trees on vertex set [n] = {1,2,...,n} rooted at 1 with one marked inversion (an inversion is a pair (i,j) with i > j and j a descendant of i in the tree). Here is a bijection from the title graphs (on [n]) to these marked trees. A title graph has exactly one cycle. There is a unique path from vertex 1 to this cycle, first meeting it at k, say (k may equal 1). Let i and j be the two neighbors of k in the cycle, with i the larger of the two. Delete the edge k<->j thereby forming a tree (in which j is a descendant of i) and take (i,j) as the marked inversion. To reverse this map, create a cycle by joining the smaller element of the marked inversion to the parent of the larger element. a(n) = binomial(n-1,2)*A129137(n). This is because, on the above marked trees, the marked inversion is uniformly distributed over 2-element subsets of {2,3,...,n} and so a(n)/binomial(n-1,2) is the number of trees on [n] (rooted at 1) for which (3,2) is an inversion. - David Callan, Mar 30 2007

			E.g., a(4)=15 because there are three different (labeled) 4-cycles and 12 different labeled graphs with a 3-cycle and an attached, external vertex.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
C. L. Mallows, Letter to N. J. A. Sloane, 1980.
R. J. Riddell, Contributions to the theory of condensation, Dissertation, Univ. of Michigan, Ann Arbor, 1951.

Alois P. Heinz, Table of n, a(n) for n = 1..300 (terms n = 1..50 from Washington G. Bomfim)
Federico Ardila, Matthias Beck, Jodi McWhirter, The Arithmetic of Coxeter Permutahedra, arXiv:2004.02952 [math.CO], 2020.
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 133.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
Younng-Jin Kim and Woong Kook, Winding number and Cutting number of Harmonic cycle, arXiv:1812.04930 [math.CO], 2018.
C. L. Mallows, Letter to N. J. A. Sloane, 1980
Marko Riedel et al., Non-isomorphic, connected, unicyclic graphs, Math Stackexchange, November 2018. (Proof of closed form by Cauchy Coefficient Formula / Lagrange Inversion.)
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.

A diagonal of A343088.
Cf. A000272 = labeled trees on n nodes; connected labeled graphs with n nodes and n+k edges for k=0..8: this sequence, A061540, A061541, A061542, A061543, A096117, A061544, A096150, A096224.
Cf. A001429 (unlabeled case), A052121.
For any number of edges we have A001187, unlabeled A001349.
This is the connected and covering case of A116508.
For #edges <= #nodes we have A129271, covering A367869.
For #edges > #nodes we have A140638, covering A367868.
This is the connected case of A367862 and A367863, unlabeled A006649.
The version with loops is A368951, unlabeled A368983.
This is the covering case of A370317.
Counting only covering vertices gives A370318.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
Cf. A062734, A098909, A123527, A129137, A133686, A143543, A323818, A367916, A367917, A369191, A369197.

egf:= -1/2*ln(1+LambertW(-x)) +1/2*LambertW(-x) -1/4*LambertW(-x)^2:
a:= n-> n!*coeff(series(egf, x, n+3), x, n):
seq(a(n), n=1..25);  # Alois P. Heinz, Mar 27 2013

nn=20; t=Sum[n^(n-1) x^n/n!, {n,1,nn}]; Drop[Range[0,nn]! CoefficientList[Series[Log[1/(1-t)]/2-t^2/4-t/2, {x,0,nn}], x], 1]  (* Geoffrey Critzer, Oct 07 2012 *)
a[n_] := (n-1)!*n^n/2*Sum[1/(n^k*(n-k)!), {k, 3, n}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jan 15 2014, after Vladeta Jovovic *)
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[#]==n&&Length[csm[#]]<=1&]],{n,0,5}] (* Gus Wiseman, Feb 19 2024 *)

# Warning: Floating point calculation. Adjust precision as needed!
from mpmath import mp, chop, gammainc
mp.dps = 200; mp.pretty = True
for n in (1..100):
    print(chop((n^(n-2)*(1-3*n)+exp(n)*gammainc(n+1, n)/n)/2))
# Peter Luschny, Jan 27 2016

The number of labeled connected graphs with n nodes and m edges is Sum_{k=1..n} (-1)^(k+1)/k*Sum_{n_1+n_2+..n_k=n, n_i>0} n!/(Product_{i=1..k} (n_i)!)* binomial(s, m), s=Sum_{i..k} binomial(n_i, 2). - Vladeta Jovovic, Apr 10 2001
E.g.f.: (1/2) Sum_{k>=3} T(x)^k/k, with T(x) = Sum_{n>=1} n^(n-1)/n! x^n. R. J. Riddell's thesis contains a closed-form expression for the number of connected graphs with m nodes and n edges. The present series applies to the special case m=n.
E.g.f.: -1/2*log(1+LambertW(-x))+1/2*LambertW(-x)-1/4*LambertW(-x)^2. - Vladeta Jovovic, Jul 09 2001
Asymptotic expansion (with xi=sqrt(2*Pi)): n^(n-1/2)*[xi/4-7/6*n^(-1/2)+xi/48* n^(-1)+131/270*n^(-3/2)+xi/1152*n^(-2)+4/2835*n^(-5/2)+O(n^(-3))]. - Keith Briggs, Aug 16 2004
Row sums of A098909: a(n) = (n-1)!*n^n/2*Sum_{k=3..n} 1/(n^k*(n-k)!). - Vladeta Jovovic, Oct 26 2004
a(n) = Sum_{k=0..C(n-1,2)} k*A052121(n,k). - Alois P. Heinz, Nov 29 2015
a(n) = (n^(n-2)*(1-3*n)+exp(n)*Gamma(n+1,n)/n)/2. - Peter Luschny, Jan 27 2016
a(n) = A062734(n,n+1) = A123527(n,n). - Gus Wiseman, Feb 19 2024

More terms from Vladeta Jovovic, Jul 09 2001

cp's OEIS Frontend

User: Qing-Hu Hou

A320159 Number of positive integers x < prime(n)/2 such that (x^2 mod prime(n)) > (4*x^2 mod prime(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A154404 Number of ways to express n as the sum of an odd prime, a positive Fibonacci number and a Catalan number.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A057500 Number of connected labeled graphs with n edges and n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions