检索结果-内蒙古大学图书馆

A diluted version of the problem of the existence of the Hofstadter sequence

JOURNAL OF DIFFERENCE EQUATIONS AND APPLICATIONS 2025年第1期31卷 48-65页

作者： Deane, Jonathan H. B. Gentile, Guido Univ Surrey Dept Math Guildford GU2 7XH England Univ Roma Tre Dipartimento Matemat & Fis Rome Italy

We investigate the conditions on an integer sequence f(n)f(n), n is an element of N, with f(1) = 0, such that the sequence q(n), computed recursively via q(n) = q(n-q(n-1)) + f(n), with q(1) = 1, exists. We prove that f(n) is 'slow', that is, f(n+1) - f(n) is an element of {0,1}, n >= 1, is a sufficient but not necessary condition for the existence of sequence q. Sequences q defined in this way typically display non-trivial dynamics: in particular, they are generally aperiodic with no obvious patterns. We discuss and illustrate this behavior with some examples.

关键词： nested recursion Hofstadter q-sequence existence of solutions nonlinear dynamics

来源：评论

学校读者我要写书评

暂无评论

nested recursions with ceiling function solutions

引用

JOURNAL OF DIFFERENCE EQUATIONS AND APPLICATIONS 2012年第6期18卷 1015-1026页

作者： Isgur, Abraham Kuznetsov, Vitaly Tanny, Stephen M. Univ Toronto Dept Math Toronto ON M5S 2E4 Canada

Consider a nested, non-homogeneous recursion R(n) defined by R(n) = Sigma R-k(i=1)(h - s(i) - Sigma R-pi(j=1)(n - q(ij))) + nu, with c initial conditions R(1) =xi(1) > 0, R(2) = xi(2) > 0, ... , R(c) = xi(c) > 0, where the parameters are integers satisfying k > 0, p(i) > 0, and a(ij) > 0. We develop an algorithm to answer the following question: for an arbitrary rational number r/q, is there any set of values for k;pi;si;aij and n such that the ceiling function inverted right perpendicularrn/qeinverted left perpendicular is the unique solution generated by R(n) with appropriate initial conditions? We apply this algorithm to explore those ceiling functions that appear as solutions to R(n). The pattern that emerges from this empirical investigation leads us to the following general result: every ceiling function of the form inverted right perpendicularrn/qeinverted left perpendicular is the solution of infinitely many such recursions. Further, the empirical evidence suggests that the converse conjecture is true: if inverted right perpendicularrn/qeinverted left perpendicular is the solution generated by any recursion R(n) of the form above, then r = 1. We also use our ceiling function methodology to derive the first known connection between the recursion R(n) and a natural generalization of Conway's recursion.

关键词： nested recursion Conolly sequence Conway sequence ceiling function

来源：评论

学校读者我要写书评

暂无评论

CONSTRUCTING NEW FAMILIES OF nested recursionS WITH SLOW SOLUTIONS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2016年第2期30卷 1128-1147页

作者： Isgur, A. Lech, R. Moore, S. Tanny, S. Verberne, Y. Zhang, Y. Univ Toronto Dept Math Toronto ON M5S 2E4 Canada

A recurring theme in nested recursions research has been the search for recursion families. By a recursion family we mean a collection of recursions with a common or at least highly similar structure, and where, with appropriate (but usually different) initial conditions for each recursion, their respective solutions behave similarly in key respects. Our key result is a general method for generating a family of recursions with slow solutions from arty nested recursion of the form either R(n) = R(n - s(1) - R(n - a(1))) + R(n - s(2) R(n - a(2))) (a two -term generalized Conolly recursion) or R(n) = R(n - s(1) - R(n - a(1))) + R(-t(1) + R(n - b(1))) (a generalized Conway recursion) so long as the recursion with which we start, together with its initial conditions, has a known slow solution. We apply this method to discover new families of recursions with slow solutions based on the well-known Hofstadter V and Conway recursions, respectively.

关键词： nested recursion Hofstadter sequence V sequence Conway sequence slowly growing solution family of nested recursions

来源：评论

学校读者我要写书评

暂无评论

Sums of ceiling functions solve nested recursions

引用

JOURNAL OF DIFFERENCE EQUATIONS AND APPLICATIONS 2012年第12期18卷 1967-1977页

作者： Drabek, Rafal Isgur, Abraham Kuznetsov, Vitaly Tanny, Stephen M. Univ Toronto Dept Math Toronto ON M5S 2E4 Canada

It is known that, for given integers s >= 0 and j > 0, the nested recursion R(n) = R(n - s - R(n - j)) + R(n - 2j - s - R(n - 3j)) has a closed-form solution for which a combinatorial interpretation exists in terms of an infinite, labelled tree. For s = 0, we show that this solution sequence has a closed form as the sum of ceiling functions C(n) = Sigma(j-1)(i=0) inverted right perpendicularn - i/2jinverted left perpendicular. Furthermore, given appropriate initial conditions, we derive necessary and sufficient conditions on the parameters s(1), a(1), s(2) and a(2) so that C(n) solves the nested recursion R(n) = R(n - s(1) - R(n - a(1))) + R(n - s(2) - R(n - a(2))).

关键词： nested recursion ceiling function formal satisfaction equivalence class

来源：评论

学校读者我要写书评

暂无评论

'Golomb-like' nested recursions with Beatty function solutions

引用

JOURNAL OF DIFFERENCE EQUATIONS AND APPLICATIONS 2013年第3期19卷 372-383页

作者： Isgur, Abraham Kim, Michael Jong Milcak, Juraj Tanny, Stephen Univ Toronto Dept Math Toronto ON M5S 2E4 Canada

Golomb showed that for k, a fixed positive integer, one solution of the nested recursion is the Beatty sequence , where is the positive root of the quadratic polynomial . We prove a natural generalization of this result: if r is any real root of some polynomial of degree d>1 with integer coefficients, then the Beatty function is a solution of a d-nested' analogue of Golomb's original 2-nested' recursion.

关键词： Golomb recursion Beatty sequence nested recursion fractional part primary 11B37 secondary 11B83

来源：评论

学校读者我要写书评

暂无评论

A combinatorial approach for solving certain nested recursions with non-slow solutions

引用

JOURNAL OF DIFFERENCE EQUATIONS AND APPLICATIONS 2013年第4期19卷 605-614页

作者： Isgur, Abraham Kuznetsov, Vitaly Tanny, Stephen M. Univ Toronto Dept Math Toronto ON M5S 2E4 Canada

We define the generalized Golomb triangular recursion by g(j,s,lambda)(n) = g(j,s,lambda)(n - s - g(j,s,lambda)(n - j)) + lambda(j). For particular choices of the initial conditions, we show that the solution of the recursion is a non-slow monotone sequence for which we can provide a combinatorial interpretation in terms of a weighted count of the leaves of a certain labelled infinite tree. We discover that more than one such tree interpretation is possible, leading to different choices of the initial conditions and alternative solutions that are closely related. In the case lambda = 1, the initial conditions for these alternative tree interpretations coincide and we derive explicit closed forms for the solution sequence and its frequency function.

关键词： nested recursion slowly growing sequence non-homogeneous Conolly recursion Golomb triangular recursion

来源：评论

学校读者我要写书评

暂无评论

nested RECURRENCE RELATIONS WITH CONOLLY-LIKE SOLUTIONS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2012年第1期26卷 206-238页

作者： Erickson, Alejandro Isgur, Abraham Jackson, Bradley W. Ruskey, Frank Tanny, Stephen M. Univ Victoria Dept Comp Sci Victoria BC V8W 3P6 Canada Univ Toronto Dept Math Toronto ON H5S 2E4 Canada San Jose State Univ Dept Math San Jose CA 95192 USA

A nondecreasing sequence of positive integers is (alpha, beta)-Conolly, or Conolly-like for short, if for every positive integer m the number of times that m occurs in the sequence is alpha + beta r(m), where r(m) is 1 plus the 2-adic valuation of m. A recurrence relation is (alpha, beta)-Conolly if it has an (alpha, beta)-Conolly solution sequence. We discover that Conolly-like sequences often appear as solutions to nested (or meta-Fibonacci) recurrence relations of the form A(n) = Sigma(k)(i=1) A(n-s(i)-Sigma(pi)(j=1) A(n-a(ij))) with appropriate initial conditions. For any fixed integers k and p(1), p(2), ..., p(k) we prove that there are only finitely many pairs (alpha, beta) for which A(n) can be (alpha, beta)-Conolly. For the case where alpha = 0 and beta = 1, we provide a bijective proof using labeled infinite trees to show that, in addition to the original Conolly recurrence, the recurrence H(n) = H(n - H(n - 2)) + H(n - 3 - H(n - 5)) also has the Conolly sequence as a solution. When k = 2 and p(1) = p(2), we construct an example of an (alpha, beta)-Conolly recursion for every possible (alpha, beta) pair, thereby providing the first examples of nested recursions with p(i) > 1 whose solutions are completely understood. Finally, in the case where k = 2 and p(1) = p(2), we provide an if and only if condition for a given nested recurrence A(n) to be (alpha, 0)-Conolly by proving a very general ceiling function identity.

关键词： self-referencing recursion nested recursion slowly growing sequence Conolly-like ruler function meta-Fibonacci bijective proof infinite trees ceiling function identity

来源：评论

学校读者我要写书评

暂无评论

Partial and nested Recursive Function Definitions in Higher-order Logic

引用

JOURNAL OF AUTOMATED REASONING 2010年第4期44卷 303-336页

作者： Krauss, Alexander Tech Univ Munich Inst Informat Munich Germany

Based on inductive definitions, we develop a tool that automates the definition of partial recursive functions in higher-order logic (HOL) and provides appropriate proof rules for reasoning about them. Termination is modeled by an inductive domain predicate which follows the structure of the recursion. Since a partial induction rule is available immediately, partial correctness properties can be proved before termination is established. It turns out that this modularity also facilitates termination arguments for total functions, in particular for nested recursions. Our tool is implemented as a definitional package extending Isabelle/HOL. Various extensions provide convenience to the user: pattern matching, default values, tail recursion, mutual recursion and currying.

关键词： Proof assistants Partial functions nested recursion

来源：评论

学校读者我要写书评

暂无评论

nested PLS

引用

ARCHIVE FOR MATHEMATICAL LOGIC 2011年第3-4期50卷 395-409页

作者： Arai, Toshiyasu Chiba Univ Grad Sch Sci Inage Ku Chiba 2638522 Japan

In this note we will introduce a class of search problems, called nested Polynomial Local Search (nPLS) problems, and show that definable NP search problems, i.e., Sigma(b)(1)-definable functions in T(2)(2)e character... 详细信息

关键词： Search problems Bounded arithmetic nested recursion

来源：评论

学校读者我要写书评

暂无评论

Discovering linear-recurrent solutions to Hofstadter-like recurrences using symbolic computation

引用

JOURNAL OF SYMBOLIC COMPUTATION 2018年 87卷 99-126页

作者： Fox, Nathan Rutgers State Univ Dept Math New Brunswick NJ 08901 USA

The Hofstadter Q-sequence, with its simple definition, has defied all attempts at analyzing its behavior. Defined by a simple nested recurrence and an initial condition, the sequence looks approximately linear, though with a lot of noise. But, it is unknown whether the sequence is even infinite. In the years since Hofstadter published his sequence, various people have found variants with predictable behavior. Commonly, the variant sequences eventually satisfy linear recurrences. Proofs of such behaviors are inductive and highly automatable. This suggests that a search for more sequences like these may be fruitful. In this paper, we develop an algorithm to search for these sequences. Using this algorithm, we determine that such sequences come in infinite families that are themselves plentiful. In fact, there are hundreds of easy to describe families based on the Hofstadter Q-recurrence alone. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： nested recursion Recurrences Quasipolynomials Integer sequences

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：