OPEN PROBLEMS from the FLAGSTAFF CONFERENCE-- June 2002

Proposer

Brief Statement of Problem

Further notes

Curtis Cooper & Michael Wiemann

Fix m: Define

x_-1= 0, x_n= x^m- x_{n
- 1}

Let P_m(n) be a solution to the above

Find a closed formula for P_m(n)

*1 Paper

*2 Known formulations of P_m(n)

Glenn Hurlbert & Rob Hochberg

Inscribe n-gon in semi-circle

Require integer sides

If n=3==>Pythagoreean triples

If n=4=>Pythagoreean Quadruple

Are there infinitely many n with nested Pythagoreean n-tuples?

Eric Egge & Toufik Mansour

Fix n. Let S_n be all n-permutations

Let R be a set of Permutations

Let S_n(R)=(s in S_n: s avoids R)

Find formula for |S_n(R)|

Find |S_n(R)| when R [avoids/contains] 123 and [contains/avoids] r>1 other patterns.

*3 Definition of avoidance

*4. Applications

*5. Known results on |S_n(R)|

Arthur Benjamin &

Jennifer Quinn

Lemma: F_n and L_n count the number of domino-square tilings of n x 1 boards/bracelets.

Using this lemma find proofs for all formula in Vajda

*6. Precise statement of lemma

*7. What is known / references

Heiko Harborth

Take an empty Pascals triangle

Fill the 2 diagonal borders with finite # 1,0

Fill rest of triangle by addition modulo 2

Is every n equal to the number of 1s in triangle for some initial borders?

Given n, Find minimal borders such that # 1 in Pascal triangle = n?

Clark Kimberling

1, 1, 2, 3, 5, 8, 4, 12, 6,.....

Start sequence with 1,1

If S_n /2 not in list then S_n+1=S_n / 2;

else S_n+1 = S_n+S_n-1

Is every natural number in this list?

*8. Similar problem in Crux

Heiko Harborth

Pick a base b to represent numbers in

Let S₁= a be arbitrary.

Let S_n+1 = S_n + reversal of S_n

Find a and b such that no palindrom occurs in the sequence S_n

*9. Some known facts

Heiko Harborth

Develop algorithms for magic n-gons (Generalize magic square theory)

*10. Some elementary facts & examples

Daniel Fielder

A Deception problem

*11. See footnote for full statement

Russell Hendel

Given k, Solve F_n = P_k,m for (n,m)

Solve generalizations

*12. Acknowledgement to Dean

*13. A long list of references

Larry Somer

Let u_n+2 = a u_n+1 + b u_n ;

Let u₀=2 and u₁ be arbitrary

(For u₁=1, a=b=1, we obtain the Lucas numbers)

Discuss the density of u_n with prime factors congruent to 1 modulo 4

*14 Related results

Notes

*1 See section 8 of Divisibility of an F-L Type Convolution, section 8 by the authors RETURN

*2 It is known that

P₀(n)=1 -iff(n is odd,1,0), P₁(n)=n/2 + if(n odd,1,0)/2, P₂(n)=n²/2 +n/2

P_m(n) = 0.5 *( (n+1)^m -S C(m,i) P_m-i(n))

Where C(m,i) is the binomial coefficient, m chose 1, and iff(Condition,value1,value2) equals value1 if condition is true and equals value2 otherwise RETURN

*3 Let S_n denote the set of all permutations of {1,...,n} written in one-line notation. Suppose p₁, p₂ in S_n. We say

p₁ avoids p₂ if p₁ contains no subsequence with all the same pairwise comparisons of p₂.

For example, 214538769 avoids 312 and 2413 but does not avoid 1243 because of the subsequence 2586 RETURN

*4. Pattern avoidance has applicability to the areas of Singularities in Shubert varieties, Chebychev Polynomials of the 2nd kind, rook polynomials for a rectangular board and various sorting algorithms RETURN

*5. Egge and Mansour in their paper 132-avoiding Two-stack Sortable Permutations, Fibonacci Numbers and Pell Numbers, found explicit formula for |S_n(R)| (Where | | denotes cardinality) when R [avoids|contains] 123 but [contains\avoids] r=1 other patterns. The proofs however involved generating functions.

Hence we have two problems: (a) Find alternate proofs using combinatoric interpretations, (b) find explicit formula for |S_n(R)| for r >1. RETURN

*6. Define a domino and square respectively as a 2 x 1 and 1 x 1 board. Then F_n is the number of distinct domino-square tilings of an n x 1 board and L_n is the number of distinct tilings of an n x 1 bracelet (Where a bracelet is an n x 1 board whose first and last squares are adjacent). RETURN

*7. Roughly 88% of the formulae in Vajda have been proved combinatorically. See the followin references

Benjamin A.T. and Quinn J.J. Recounting Fibonacci and Lucas Identities, College Math Journal 30.5, 1999 Benjamin A.T. and Quinn J.J. Random approaches to Fibonacci Identities, Amer Math Mon;107.6,2000

Benjamin A.T. & Quinn J.J. & F.E. Su Counting on continued Fractions, Math Magazine, 73.2, 2000

Benjamin A.T. & Quinn J.J & F.E. Su. General Fibonacci Identities thru Phased Tilings, Fibonacci Quarterly 38.3, 2000

Vajda, S Fibonacci & Lucas Numbers & the Golden Section: Theory and Applications. Wiley & Sons, NY 1989 RETURN

*8. The following similar problem appeared in Crux Mathematicorum

Consider the following sequence 1,3,9,4,2,5,18....

Let a(n) = Int(a(n-1) / 2) if this member is not already there

Let a(n) = 3a(n-1) otherwise

Show that every natural number occurs in the sequence a(n) RETURN

*9. There is no solution for base 10. Solutions are known for bases that are powers of 2. RETURN

*10 The following magic hexagon was presented

Some elementary necessary conditions for magic n-gons are the following

If an n-gon, with r rows, is filled with 1,...,n then each row must sum to
n(n+1) / (2r) In particular n(n+1) / (2r) must be integral. For each shape (hexagon, triangles, octagons) this places restrictions. RETURN

*11. Here is the full statement of the problem

- Throughout let n vary over the set (1,2,3)

- Let p be a prime

- Let f_n(x) be irreducible polynomials modulo p

- Let r_n be positive integers

- Let t_n be the smallest solutions of the simultaneous eq. 1 - x^tn = 0 (mod f_n(x) ^rn)

Show that the above implies

1 - x ^LCM(tn) = 0 mod (Product f_n(x) ^rn) RETURN

*12. This problem was motivated by one of the opening remarks of the Dean of Northern Arizona University that

“ This is the 10th Fibonacci conference

1+2+...+10=55

F₁₀ = 55"

An obvious generalization is

Find all pairs (n,m) such that F_n = T_m, where Tm is the m-th triangular number

More generally if G_n and H_m are arbitrary sequences defined by a recursive equation

find all (n,m) such that G_n = H_m. RETURN

*13. Special cases of the problem have been solved. Florian Luca was kind enough to supply a Bibliography of papers

Ming, L. On triangular Fibonacci numbers, Fibo. Quart. 27 (1989),

Ming, L. On triangular Lucas numbers, Applications of Fibonacci Numbers

vol. 4, Editors, Bergum, Horadam, Philippou, Kluwer Acad. Publ. Dordrech,

the Netherlands, 1991, 98

Ming, L. Pentagonal numbers in the Fibonacci sequence, Appl. of

Fibonacci numbers, vol. 6, Kluwer, Dordrecht, the Netherlands, 1994,

349-354.

Ming L., Pentagonal numbers in the Lucas sequence, Portugaliae Math. 53

(1996), 352-329.

What these papers have in common is that the proof if Jacobi symbol based

and they provide succesive refinements of an idea originated in

J.H.E. Cohn, On square Fibonacci numbers, J. London Math. Soc. 39

(1964), 537-540.

Other papers are

Wayne McDaniel, Pronic Fibonacci and Lucas numbers, Fibo. Quart. 1998, 56-59 &

60-62;

Luca, Florian, Appl. of Fibonacci numbers, vol. 8, Kluwer,

Dordrecht, the Netherlands, 1999, 241-249).

General finiteness results for F_n=P(x) or L_n=P(x) with P a polynomial of

degree >1 appear in

Nemes, Petho: Polynomial values in Linear Recurrences,

II, Journal of Number Theory 24 (1986), 47-53

I found the following relevant problem B-875 FQ 37.2 1999; 3 is the only solution to T_n = a Fermat Number RETURN

*14. Somer proved that If b is a square and a has prime factors congruent to 1 modulo 4 then

all u_n,n>2, have prime factors congruent to 1 modulo 4.

Divisibility of the Lucas numbers by prime factors congruent to 1 modulo 4 has been studied extensively and there are many known numerical results. The above problem is an attempt to generalize. RETURN

Web Page prepared by Russell Jay Hendel.; Comments/Corrections/References?