#  On the impact of robot personalization on human-robot interaction: A review

Jinyu Yang<EMAIL_ADDRESS>Technical University of MunichGermany ,  M. Sc.
Camille Vindolet<EMAIL_ADDRESS>Institute for Cognitive
SystemsTechnical University of MunichGermany ,  Dr.-Ing. Julio Rogelio
Guadarrama Olvera<EMAIL_ADDRESS>Institute for Cognitive
SystemsTechnical University of MunichGermany and  Prof. Dr. Gordon Cheng
<EMAIL_ADDRESS>Institute for Cognitive SystemsTechnical University of
MunichGermany

(2023; 27 January 2023)

###### Abstract.

This study reviews the impact of personalization on human-robot interaction.
Firstly, the various strategies used to achieve personalization are briefly
described. Secondly, the effects of personalization known to date are
discussed. They are presented along with the personalized parameters,
personalized features, used technology, and use case they relate to. It is
observed that various positive effects have been discussed in the literature
while possible negative effects seem to require further investigation.

Human-robot interaction, robot personalization, socially assistive robotics,
social robotics, human-centred design

††copyright: acmcopyright††journalyear: 2023††conference: ; March 13, 2023;
Stockholm, Sweden††price: ††ccs: Human-centered computing Collaborative and
social computing††ccs: Security and privacy Database and storage
security††ccs: Computing methodologies Artificial intelligence††ccs: Applied
computing

##  1\. Introduction

Nowadays, robots are expected to evolve alongside humans and to interact more
closely with them. In particular, socially assistive robots (SAR) should be
capable of social interactions and are presented as a potential solution for
the growing need for assistance in domains such as healthcare, education, and
elderly care (Rouaix et al., 2017). They should, for example, perform various
household tasks, provide companionship to the elderly, assist children in
learning (Tanev and Lekova, 2022), deliver meals (Dino et al., 2019), or guide
people in tours of shopping (Nithya Priya et al., 2021) or museums.

As robots are expected to become increasingly integrated into people’s daily
lives, it seems important to create more natural and personalized interactions
between humans and robots. Indeed, they should become companions that provide
both mental and physical support. This type of interactions require an
emotional intelligence from the robot side with a capacity to adapt to the
user’s state (Durães et al., 2018). Thus, personalization is one of the
current field of research in HRI and more specifically in SAR. It aims to
enable robots to understand human needs and preferences and to correctly adapt
to them. For example, personalized robots should recognize and respond
accordingly to the users social interactions, nonverbal behaviors, or culture.
Personalization is said to improve the user experience, encourage social
acceptance of the robot, and lead to more effective social interactions by
adapting the behavior, appearance and interaction patterns of robots to the
individuals needs and preferences.

Many strategies for achieving personalization have been investigated. Mehdi
Hellou et al. (2021) (Hellou et al., 2021) presented a review of the employed
methods, to date, to create robot personalization.

Personalization can influence differently the user perception of the quality
of the interaction and of the system trustworthiness. It can help improving
the match between the user expectations and the robot behavior. This paper
reviews the findings on the impact of personalization in HRI, in order to
acquire a more comprehensive understanding of how personalization affects the
interaction experience and provided service that better fulfills the
requirements of the user. Examples of current personalization strategies are
provided in section 2. Personalizing a robot for different scenarios and work
contexts is possible in a variety of ways. The consequences of various
personalization are studied in section 3. Section 4 discusses possible
directions for further research into the effects of personalization.

##  2\. Personalized Robot Strategies and use cases

|  Analysed Parameters |  Personalized Features |  Technology, Hardware and Sensors |  Use Cases/ Purpose |  The Effects of personalization
---|---|---|---|---|---
M. K. Lee et al. (2012) (Lee et al., 2012) |  Users’ snack selection, service-patterns and previous behaviour of the robot |  Social interactions and small talk topics by robot |  Snack ordering website, Snackbot, SICK LIDAR, etc. |  Delivering snacks |  Reinforcement of people’s rapport, cooperation and engagement with robot
D. Portugal et al. (2015) (Portugal et al., 2015) |  Users’ emotional state and personal preferences |  Robot’s service: movement, navigation, emotional companionship, etc. |  Service-Oriented Architecture (SOA), service-oriented architecture, etc. |  Home care of the elder |  Not mentioned
G. Gordon et al. (2016) (Gordon et al., 2016) |  Emotional and game state |  Game-related responses (instructions, prompts) and emotional responses |  Tega robot platform, Robot Operating System (ROS), etc. |  Regulating the student’s emotional state while providing them with second language tutoring |  Significant increase in children’s engagement and valence
C. E. Clabaugh (2017) (Clabaugh, 2017) |  Frequency of elicitation (asking learning-sensitive questions) |  Robotic tutor’s elicitation of learning-sensitive information |  Not mentioned |  Robot tutor for personalized education |  Improved stimulation and increased trust towards the robot
N. Churamani et al. (2017) (Churamani et al., 2017) |  User utterance and personal information |  Utterance by robot |  NICo, Humanoidly Speaking Scenario, Face and Speech Recognition, etc. |  Teaching the robot to recognize different objects |  Improved impressions of the robot for the users
D. Leyzberg et al. (2018) (Leyzberg et al., 2018) |  Participants’ level of skill acquisition |  Ordering of the interchangeable lesson chapters |  The extended Bayesian Knowledge Tracing (BKT) family of student models with camera and microphone |  Rearrange curriculum while completing an English Language Learning educational task |  Increased learning gains
C. Clabaugh et al. (2019) (Clabaugh et al., 2019) |  Children’s behaviour during the game (Whether mistakes were made, help requested, etc.) |  Level of challenge and feedback |  Tega robot platform, electrodermal activity sensors, etc. |  Social and educational development of children with ASD |  Improved learning and evidence of longer-term engagement
H. W. Park et al. (2019) (Park et al., 2019) |  Users’ behavior and affective arousal state |  Lexical and syntactic complexity in storytelling |  Tega robot platform, electrodermal activity sensors, etc. |  Learning companion |  Increase of Children’s engagement, improved learning, increased use of the target words, etc.
S. Schneider and Franz Kummert (2021) (Schneider and Kummert, 2021) |  Level of automation |  Robot’s service: propose different activities |  Database of different exercises, session controller, 3D depth sensor, etc. |  Assisting the user in exercising |  Higher trust and perceived as more competent
M. E. U. Ligthart et al. (2022) (Ligthart et al., 2022) |  Children’s interest, preferences and choices |  Serial narrative dialog |  Google’s dialog flow, onboard microphone, Redis database, etc. |  Communicating with children in dialogue |  Longer interest for the robot, better engagement
Table 1. Summary of the papers analyzed in this review.

As discussed in the previous section, there are various use cases of SAR, such
as visiting of and caring for the elderly, helping disabled people with
rehabilitation training, assisting and instructing children in their studies,
among others. As a result, there is not a single solution for personalizing a
robot. The robot’s personalization and the researchers’ design can vary from
simple methods, such as choosing between several pre-defined dialogue or
actions the one that fit the best the user needs and preferences, to more
complex algorithms and technology that, based on multisensory integration and
complex models, generate appropriate robot behaviors. The examples studied in
this article are listed in Table 1. The table presents in order of the
columns, the article, the experiment parameters taken into account for the
personalization, the personalized robot features, the encountered technology,
the use case and purpose of the personalization and its effects.

Personalization can be, for example, pre-programming the robot’s speech or
actions based on user data. To investigate how to build and maintain rapport
between robots and people, Min Kyung Lee et al. (2012) (Lee et al., 2012)
designed a snack delivering robot and created a personalization strategy that
involved developing pre-defined discussions and responses, later selected
based on the user’s prior interactions with the robot and with its delivery
service. The robot will present multiple discussions to the user depending on
the user’s snack selection pattern, and service usage pattern, and on the
robot’s past behavior (as indicated in figure 1). Based on a record of defects
and faults maintained in the service database, the robot also apologizes for
any errors that have happened.

More recently, researchers have developed complex algorithms and techniques to
create personalized robot strategies. These algorithms frequently require a
combination of data, such as how the participant interacts with the robot, the
responses given to the robot’s activities (e.g., facial expressions, etc.),
and the history of previous interactions.

David Portugal et al. (2015) (Portugal et al., 2015) provided a summary of the
techniques developed in the SocialRobot project. In this project, a mobile
robot platform was created in conjunction with virtual social care
technologies in order to enhance elder’s quality of life and fulfill their
individual needs. They created a model based on service-oriented architecture
(SOA) and used social care community network to manage and coordinate user
profiles for proactive and individualized care. The database could dynamically
be adjusted in order to update user preferences.

Goren Gordon et al. (Gordon et al., 2016) created an integrated system of
affective policy learning and autonomous social robots to investigate how
effectively personalized robots regulate students’ affective states in one-on-
one tutorials. Various states were specified as parameters in the affective
policy: the child’s valence, engagement, as well as information about whether
they correctly answered the questions and if they had previously interacted
with the robot. A state-action reward state-action (SARSA) algorithm and an
epsilon-greedy algorithm are used to determine the robot’s action states.

Hae Won Park et al. (Park et al., 2019) studied how robots can assist young
learners in optimizing their learning results. To manage the selection of
robot behaviors, they created an affective personalization policy. The user’s
behavior (their question answering behavior during the robot’s story
narration), their affective arousal state (their facial muscle activation
illustrating their expressiveness and arousal level), the robot’s actions (the
lexical and syntactic complexity of a given sentence in storytelling), the
rewards the robot earned for its activities (the new lexical and syntax
learning), and the changes in the user’s state were organized into different
episodes that were trained by Q-Learning, resulting in a personalized policy
for each user.

Caitlyn Clabaugh et al. (Clabaugh et al., 2019) developed a hierarchical
framework for Human Robot Learning to manage the behavior of personalized
robots in their study of assistive robots serving children with autism
spectrum disorders (ASD). In this framework, the robot’s interventions were
subdivided into deﬁned state-action sub-spaces, with five controllers each
responsible for a subset of actions and describing abstract action categories
such as disclosure, promise, instruction, feedback, and inquiry. These
controllers were combined with algorithms including Q-Learning to ensure that
the robot’s feedback and instruction challenge levels could be personalized to
each child’s particular learning style.

Figure 1. An overview of the personalized topics proposed by Min Kyung Lee et
al. (Lee et al., 2012)

##  3\. The impact of personalization

Personalization, as discussed in the preceding section, has become an
increasingly important component of HRI. Additionally, it has created new
possibilities for SAR by enabling more efficient and satisfying user
experiences. However, it is necessary to examine the potential impacts of
personalization. This section examines both positive and negative effects of
personalization including potential long-term ones.

###  3.1. Positive Impact

Caitlyn E. Clabaugh et al. (2017) (Clabaugh, 2017) analysed the elicitation of
learning-sensitive information by a robotic tutor that would be utilised by an
interactive machine learning approach for personalized education. They focused
on the relationship between the frequency of elicitation and human learners’
impressions of tutorial interactions. The study showed that more frequent
elicitation of learning-sensitive information by the robot tutor led to a
significant increase in participants’ interaction with the robot tutor, and
that the robot tutor was perceived to be more interactive and affectionate,
and was better trusted.

A study on the impact of various SAR automation levels on user perception of
the system in an exercise scenario was presented by Sebastian Schneider et al.
(2021) (Schneider and Kummert, 2021). According to the study, adaptive robots
(where an adaptive process can be initiated automatically by the robot, such
as when the robot chooses exercises for the user) are perceived as warmer and
more competent than adaptable robots (where the user adapts the system
themselves, such as when the user selects their own exercises). Users trusted
the adaptive robot substantially more than the adaptable robot. Moreover,
users who were exposed to an adaptive robot more frequently volunteered to
repeat the task.

According to Daniel Leyzberg et al. (Leyzberg et al., 2018) evaluated the
advantages personalized social robots can offer in a learning environment.
They developed a strategy to organize lessons based on a model for evaluating
students’ skill competency, with the content of the lessons related to
educational activities for native Spanish-speaking students learning English.
The study’s findings demonstrated that, assuming that all students had roughly
the same amount of prior knowledge, the group receiving the personalized
program learned more than the group receiving the non-personalized program,
which was represented in a large increase in learning gains. When compared to
learners who received non-personalized education, those who took personalized
courses produced a higher percentage of correct answers on tests.

Additionally, Mike E.U. Ligthart et al. (Ligthart et al., 2022), a memory-
based personalization strategy was developed and deployed in combination with
a continuous narrative interaction structure to address demands and keep
children from losing interest in the robot once the novelty wore off. The
research indicates that in the classic control condition, as the number of
interaction sessions increased, children’s interest in continuing the contact
began to decrease over time. However in the personalization strategy-using
condition, children’s interest in continuing the interaction remained strong.
Moreover, the children’s proximity to the robot was higher after multiple
interaction sessions when the personalization strategy was deployed, and the
strategy encouraged a closer relationship between the child and the robot.
Positive social cues were elicited more often.

The benefits of personalization have been extensively studied. Many of these
effects are connected to specific use cases and implementation contexts. They
have shown to improve the user experience and generate positive emotions.

###  3.2. Possible negative Impacts

Personalization has recently been a popular study topic. Numerous research
focused on the benefits of personalization, such as increasing the user
engagement. Those studies usually address the effects of personalization with
regard to some hypothesis and discuss whether or not personalization has a
positive impact on the features they want to study or no impact at all. For
example, Mike E.U. Ligthart et al. (Ligthart et al., 2022) notes that
personalization does not have a substantial impact on the need for familiarity
and similarity, in addition to the obvious positive effects. However, little
research has thoroughly investigated the negative impact of personalization.
As a result, this chapter presents the existing research on the topic, as well
as discusses other features of personalization that are likely to have a
negative influence.

Research and discussions on the privacy policies provided by various consumer
robot companies were performed by Anna Chatzimichali et al. (2021)
(Chatzimichali et al., 2021). According to the study, the structure, context,
and clarity of privacy provisions differ considerably between companies. This
highlights the topic of how personalization may have a negative impact on
personal privacy, user rights, and consumer rights in a context where consumer
robotics businesses are not now uniformly considering privacy issues. As
personalization depends on private data such as users’ individual preferences,
behaviors, and interaction history, the question of how to handle this
information so that privacy and user rights meet users’ requirements needs to
be addressed. This is also mentioned in Jim Torresen’s work (2021) (Torresen,
2021). He examines how sensor data collection should be limited in uncommon
and urgent situations and establishes the argument that privacy requires a
trade-off on this. In the case of robot-assisted care for the elderly, for
example, the robot is only permitted to transmit data about the elderly in
order to alert caretakers, etc., if an abnormal incident occurs.

The research by Nikhil Churamani et al. (Churamani et al., 2017) presents an
additional hypothesis regarding negative impacts. They investigated robots’
social acceptability, perceived intelligence, and likability in HRI scenarios.
Since more complicated interactions may raise certain user concerns, the study
indicated that the personalized interactive system scored worse in terms of
safety. Furthermore, because the personalized robot was equipped with speech
technology that was insufficient to support its capacity to reliably recognize
the user’s words in a noisy setting, participants did not recommend the system
for usage in the real world. This raises the possibility that personalization
might have a negative impact, since a personalized robot may be unable to deal
with the different disturbances and emergencies that come in real-life work
environments before the technology is developed, leading people to distrust
the robot and choose a more general and safe robot. In addition to human trust
in the robot, whether the robot models the human as trustworthy can have an
effect on the process and experience of HRI. According to research by Dylan P.
Losey et al. (Losey and Sadigh, 2019), modeling the human as a trusting agent
can increase HRI effectiveness, however trusting humans in this scenario are
rewarded less than humans treated as rational.

In addition to the user experience, considering the robot’s ethical and moral
feasibility is essential. For instance, the system needs to have the ability
to guarantee the user’s right as well as the fairness and verifiability of the
decision-making process (Torresen, 2021). Kathrin Pollmann et al. (Pollmann et
al., 2023) also discusses the necessity of maintaining an equilibrium between
ethical considerations and user experience design concepts in their research.
In order to avoid manipulating the user and infringing on their autonomy, it
is crucial to strive to avoid personalization methods that could result in
affective mechanisms (ie. ”guilt trip, emotional blackmail, erotic
attraction,etc.” (Pollmann et al., 2023)).

Research on the potential negatives effects of personalization is currently
lacking. The impact of personalization on security of user data privacy,
social acceptability, trust and ethical considerations of the robots should be
further researched in the future.

##  4\. Discussion and Conclusion

Whereas much research has shown the positive advantages of personalization in
various ways and for different use cases, such as creating positive emotional
impulses for users or improving tutoring efficiency, the negative implications
have not yet been properly investigated. In the previous section, some of the
potential negative features of personalization were briefly discussed: privacy
concerns, trust between human and robot, and consideration for ethics.
Furthermore, there are a variety of issues that must be addressed in a future
study on personalization.

Cong Li (2016) noted the difference between actual personalization and
perceived personalization in his work on personalization (Li, 2016). He tested
the personalization effect through the message sender’s actual personalization
process and identified that it may have misleading effects. According to his
research, a real personalization process does not always result in beneficial
results, and participants only reacted positively to messages that they
thought were more personalized, even though these messages may not have been
produced through the personalization process. He suggested that there may be
certain conditions under which a message is interpreted as personalized or
non-personalized. Unquestionably, when a message contains incorrect
information, the receiver of the message and the message are mismatched. Such
a message will cause the receiver to perceive it as non-personalized,
resulting in a negative attitude.

Another concern is human acceptance or trust towards robots. This is a
complex, multifaceted problem. The previously indicated negative human
evaluations due to the robot’s lack of competency can be linked to trust and
acceptance of the robot. Leila Takayama et al. (2009) (Takayama and Pantofaru,
2009) investigated factors influencing proxemic behaviors in HRI. It was
discovered that the size of the participant’s personal space when interacting
with a robot was related to a number of parameters. By examining the
comfortable distance between the human and the robot during HRI, S. M. Bhagya
et al. (2019) (Bhagya et al., 2019) studied human affinity preferences for
service robots. They discovered that happy and sad facial expressions on the
robot had closer proxemics, whereas anger and disgust had the opposite effect.
The comfort distance of HRI is alternatively impacted by the robot’s internal
sounds and human-like appearance. Additionally, Dylan P. Losey et al. (2019)
(Losey and Sadigh, 2019) discovered that the user experience is impacted by
the human trustworthiness or untrustworthiness settings when the robot models
people. Generally, in addition to the influence of personalization, variables
such as perceived personalization and people’s acceptance of and trust in
robots need to be considered and further investigated.

In conclusion, this review on the impact of robot personalization on HRI
presented various personalization strategies, from the most simple ones to
some more recent complex multimodal ones. It highlighted some strong
personalization benefits that have been studied in research in the past few
years. Finally this review discussed some possible negative impacts of
personalization and informed on the lack of research on this topic. Overall,
the effects of personalization seem to still required further investigation.

## References

  * (1)
  * Bhagya et al. (2019) S. M. Bhagya, P. Samarakoon, M. A. Viraj, J. Muthugala, A. G. Buddhika, P. Jayasekara, and Mohan R. Elara. 2019.  An Exploratory Study on Proxemics Preferences of Humans in Accordance with Attributes of Service Robots. In _2019 28th IEEE International Conference on Robot and Human Interactive Communication (RO-MAN)_. 1–7.  https://doi.org/10.1109/RO-MAN46459.2019.8956297 ISSN: 1944-9437.
  * Chatzimichali et al. (2021) Anna Chatzimichali, Ross Harrison, and Dimitrios Chrysostomou. 2021\.  Toward privacy-sensitive human–robot interaction: Privacy terms and human–data interaction in the personal robot era.  _Paladyn, Journal of Behavioral Robotics_ 12, 1 (Jan. 2021), 160–174.  https://doi.org/10.1515/pjbr-2021-0013 Publisher: De Gruyter Open Access.
  * Churamani et al. (2017) Nikhil Churamani, Paul Anton, Marc Brügger, Erik Fließwasser, Thomas Hummel, Julius Mayer, Waleed Mustafa, Hwei Geok Ng, Thi Linh Chi Nguyen, Quan Nguyen, Marcus Soll, Sebastian Springenberg, Sascha Griffiths, Stefan Heinrich, Nicolás Navarro-Guerrero, Erik Strahl, Johannes Twiefel, Cornelius Weber, and Stefan Wermter. 2017.  The Impact of Personalisation on Human-Robot Interaction in Learning Scenarios. In _Proceedings of the 5th International Conference on Human Agent Interaction_. ACM, Bielefeld Germany, 171–180.  https://doi.org/10.1145/3125739.3125756
  * Clabaugh et al. (2019) Caitlyn Clabaugh, Kartik Mahajan, Shomik Jain, Roxanna Pakkar, David Becerra, Zhonghao Shi, Eric Deng, Rhianna Lee, Gisele Ragusa, and Maja Matarić. 2019\.  Long-Term Personalization of an In-Home Socially Assistive Robot for Children With Autism Spectrum Disorders.  _Frontiers in Robotics and AI_ 6 (2019).  https://www.frontiersin.org/articles/10.3389/frobt.2019.00110
  * Clabaugh (2017) Caitlyn E. Clabaugh. 2017\.  Interactive Personalization for Socially Assistive Robots. In _Proceedings of the Companion of the 2017 ACM/IEEE International Conference on Human-Robot Interaction_ _(HRI ’17)_. Association for Computing Machinery, New York, NY, USA, 339–340.  https://doi.org/10.1145/3029798.3034813
  * Dino et al. (2019) Francesca Dino, Rohola Zandie, Hojjat Abdollahi, Sarah Schoeder, and Mohammad H. Mahoor. 2019\.  Delivering Cognitive Behavioral Therapy Using A Conversational Social Robot. In _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. 2089–2095.  https://doi.org/10.1109/IROS40897.2019.8968576 ISSN: 2153-0866.
  * Durães et al. (2018) Dalila Durães, Javier Bajo, and Paulo Novais. 2018\.  Characterize a Human-Robot Interaction: Robot Personal Assistance.  In _Personal Assistants: Emerging Computational Technologies_ , Angelo Costa, Vicente Julian, and Paulo Novais (Eds.). Springer International Publishing, Cham, 135–147.  https://doi.org/10.1007/978-3-319-62530-0_8
  * Gordon et al. (2016) Goren Gordon, Samuel Spaulding, Jacqueline Kory Westlund, Jin Joo Lee, Luke Plummer, Marayna Martinez, Madhurima Das, and Cynthia Breazeal. 2016.  Affective Personalization of a Social Robot Tutor for Children’s Second Language Skills.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 30, 1 (March 2016).  https://doi.org/10.1609/aaai.v30i1.9914
  * Hellou et al. (2021) Mehdi Hellou, Norina Gasteiger, Jong Yoon Lim, Minsu Jang, and Ho Seok Ahn. 2021.  Personalization and Localization in Human-Robot Interaction: A Review of Technical Methods.  _Robotics_ 10, 4 (Dec. 2021), 120\.  https://doi.org/10.3390/robotics10040120 Number: 4 Publisher: Multidisciplinary Digital Publishing Institute.
  * Lee et al. (2012) Min Kyung Lee, Jodi Forlizzi, Sara Kiesler, Paul Rybski, John Antanitis, and Sarun Savetsila. 2012\.  Personalization in HRI: A longitudinal field experiment. In _2012 7th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_. 319–326.  ISSN: 2167-2148.
  * Leyzberg et al. (2018) Daniel Leyzberg, Aditi Ramachandran, and Brian Scassellati. 2018\.  The Effect of Personalization in Longer-Term Robot Tutoring.  _ACM Transactions on Human-Robot Interaction_ 7, 3 (Dec. 2018), 19:1–19:19.  https://doi.org/10.1145/3283453
  * Li (2016) Cong Li. 2016.  When does web-based personalization really work? The distinction between actual personalization and perceived personalization.  _Computers in Human Behavior_ 54 (Jan. 2016), 25–33.  https://doi.org/10.1016/j.chb.2015.07.049
  * Ligthart et al. (2022) Mike E.U. Ligthart, Mark A. Neerincx, and Koen V. Hindriks. 2022.  Memory-Based Personalization for Fostering a Long-Term Child-Robot Relationship. In _Proceedings of the 2022 ACM/IEEE International Conference on Human-Robot Interaction_ _(HRI ’22)_. IEEE Press, Sapporo, Hokkaido, Japan, 80–89.
  * Losey and Sadigh (2019) Dylan P. Losey and Dorsa Sadigh. 2019.  Robots that Take Advantage of Human Trust. In _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. 7001–7008.  https://doi.org/10.1109/IROS40897.2019.8968564 ISSN: 2153-0866.
  * Nithya Priya et al. (2021) S. Nithya Priya, G. Swadesh, K.M Thirivikraman, Mohammed Vazeer Ali, and M. Ranjith Kumar. 2021.  Autonomous Supermarket Robot Assistance using Machine Learning. In _2021 7th International Conference on Advanced Computing and Communication Systems (ICACCS)_ , Vol. 1. 996–999.  https://doi.org/10.1109/ICACCS51430.2021.9441833 ISSN: 2575-7288.
  * Park et al. (2019) Hae Won Park, Ishaan Grover, Samuel Spaulding, Louis Gomez, and Cynthia Breazeal. 2019.  A model-free affective reinforcement learning approach to personalization of an autonomous social robot companion for early literacy education. In _Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence_ _(AAAI’19/IAAI’19/EAAI’19)_. AAAI Press, Honolulu, Hawaii, USA, 687–694.  https://doi.org/10.1609/aaai.v33i01.3301687
  * Pollmann et al. (2023) Kathrin Pollmann, Wulf Loh, Nora Fronemann, and Daniel Ziegler. 2023.  Entertainment vs. manipulation: Personalized human-robot interaction between user experience and ethical design.  _Technological Forecasting and Social Change_ 189 (April 2023), 122376\.  https://doi.org/10.1016/j.techfore.2023.122376
  * Portugal et al. (2015) David Portugal, Luís Santos, Paulo Alvito, Jorge Dias, George Samaras, and Eleni Christodoulou. 2015.  SocialRobot: An interactive mobile robot for elderly home care. In _2015 IEEE/SICE International Symposium on System Integration (SII)_. 811–816.  https://doi.org/10.1109/SII.2015.7405084
  * Rouaix et al. (2017) Natacha Rouaix, Laure Retru-Chavastel, Anne-Sophie Rigaud, Clotilde Monnet, Hermine Lenoir, and Maribel Pino. 2017.  Affective and Engagement Issues in the Conception and Assessment of a Robot-Assisted Psychomotor Therapy for Persons with Dementia.  _Frontiers in Psychology_ 8 (2017).  https://www.frontiersin.org/articles/10.3389/fpsyg.2017.00950
  * Schneider and Kummert (2021) Sebastian Schneider and Franz Kummert. 2021.  Comparing Robot and Human guided Personalization: Adaptive Exercise Robots are Perceived as more Competent and Trustworthy.  _International Journal of Social Robotics_ 13, 2 (April 2021), 169–185.  https://doi.org/10.1007/s12369-020-00629-w
  * Takayama and Pantofaru (2009) Leila Takayama and Caroline Pantofaru. 2009.  Influences on proxemic behaviors in human-robot interaction. In _2009 IEEE/RSJ International Conference on Intelligent Robots and Systems_. 5495–5502.  https://doi.org/10.1109/IROS.2009.5354145 ISSN: 2153-0866.
  * Tanev and Lekova (2022) Tanio K. Tanev and Anna Lekova. 2022.  Implementation of Actors’ Emotional Talent into Social Robots Through Capture of Human Head’s Motion and Basic Expression.  _International Journal of Social Robotics_ 14, 7 (Sept. 2022), 1749–1766.  https://doi.org/10.1007/s12369-022-00910-0
  * Torresen (2021) Jim Torresen. 2021\.  Ethical Considerations in User Modeling and Personalization. In _Proceedings of the 29th ACM Conference on User Modeling, Adaptation and Personalization_. ACM, Utrecht Netherlands, 321–322.  https://doi.org/10.1145/3450613.3457121


# Some Fibonacci-Related Sequences

Benoit Cloitre
France
<EMAIL_ADDRESS>
Jeffrey Shallit
School of Computer Science
University of Waterloo
Waterloo, ON N2L 3G1
Canada
<EMAIL_ADDRESS>
###### Abstract

We discuss an interesting sequence defined recursively; namely, sequence
A105774 from the On-Line Encyclopedia of Integer Sequences, and study some of
its properties. Our main tools are Fibonacci representation, finite automata,
and the Walnut theorem-prover. We also prove two new results about
synchronized sequences.

##  1 Introduction

Define the Fibonacci numbers $(F_{n})_{n\geq 0}$ as usual by the initial
values $F_{0}=0$, $F_{1}=1$, and $F_{n}=F_{n-1}+F_{n-2}$ for $n\geq 2$. In
2005, the first author defined an interesting sequence, A105774,
$(a(n))_{n\geq 0}$ as follows:

$a(n)=\begin{cases}n,&\text{if $n\leq 1$};\\\ F_{j+1}-a(n-F_{j}),&\text{if
$F_{j}<n\leq F_{j+1}$ for $j\geq 2$}.\end{cases}$ (1)

The first few values of $(a(n))$ are given in Table 1. Although strictly
speaking the sequence was originally defined only for $n\geq 1$, it makes
sense to set $a(0)=0$, which we have done.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$a(n)$ | 0 | 1 | 1 | 2 | 4 | 4 | 7 | 7 | 6 | 12 | 12 | 11 | 9 | 9 | 20 | 20 | 19 | 17 | 17 | 14 | 14

The sequence has an intricate fractal structure, which is depicted in Figure
1.

Figure 1: Graph of $a(n)$.

A number of properties of this sequence were stated, without proof, in the
index entry for A105774 in the On-Line Encyclopedia of Integer Sequences
(OEIS) [11]. In this paper we prove these properties, and many new ones, with
the aid of finite automata and the Walnut theorem-prover [8, 10].

We will need the Lucas numbers, $L_{n}$, defined by $L_{0}=2$, $L_{1}=1$, and
$L_{n}=L_{n-1}+L_{n-2}$ for $n\geq 2$. Recall the Binet forms:

$\displaystyle F_{n}$ $\displaystyle=(\varphi^{n}-(-1/\varphi)^{n})/\sqrt{5}$
(2) $\displaystyle L_{n}$ $\displaystyle=\varphi^{n}+(-1/\varphi)^{n}.$ (3)

In addition to studying A105774, we also prove two new results about
synchronized sequences, in Theorems 10 and 18.

##  2 Fibonacci representations

In this paper we represent the natural numbers
${\mathbb{N}}=\\{0,1,2,\ldots\\}$ in the Fibonacci (aka Zeckendorf) numeration
system [7, 12]. In this system we write $n$ as the sum of distinct Fibonacci
numbers $F_{i}$ for $i\geq 2$, subject to the condition that no two
consecutive Fibonacci numbers appear in the sum. For example,
$43=F_{9}+F_{6}+F_{2}=34+8+1$. Usually we write this representation as a bit
string $(n)_{F}=e_{1}e_{2}\cdots e_{t}$, with $e_{i}\in\\{0,1\\}$,
$e_{1}\not=0$, and $e_{i}e_{i+1}\not=1$, such that $n=\sum_{1\leq i\leq
t}e_{i}F_{t-i+2}$. For example, $(43)_{F}=10010001$. The inverse function,
mapping an arbitrary bit string (with no conditions) $x=e_{1}e_{2}\cdots
e_{t}$ to the number it represents is defined to be $[x]_{F}=\sum_{1\leq i\leq
t}e_{i}F_{t-i+2}$.

##  3 Finite automata and regular expressions

A finite automaton is a simple model of a computer. In its simplest
incarnation, a deterministic finite automaton (DFA), the automaton can be in
any one of a finite number of different states. It takes as input a finite
string over a finite alphabet, and processes its input symbol-by-symbol,
choosing the next state through a lookup table (the transition function) based
only on the current state and the next input symbol. Some of the states are
designated as accepting states; an input string is accepted if the automaton
is in an accepting state after all its symbols are processed. In this paper we
represent integers in Fibonacci representation, so we can think of the DFA as
processing integers instead of strings. Thus, a DFA is a good model to
represent a set of natural numbers; namely, the set of all integers whose
representations are accepted. In this sense, a DFA decides membership for a
set (or sequence). DFA’s are typically drawn as transition diagrams, where the
arrows represent transitions between states, double circles denote accepting
states, and single circles denote nonaccepting states.

As an example, consider the automaton in Figure 2. It takes the Fibonacci
representation of a natural number $n$ as input, and accepts if and only if
$n$ is even.

Figure 2: Fibonacci automaton for the set of even numbers.

A slightly more complicated model is the deterministic finite automaton with
output (DFAO). In this model, an output is associated with every state, and
the output on an input string $x$ is the output associated with the last state
reached after processing $x$. This model is adequate for representing
sequences over a finite alphabet; since there are only finitely many states,
only finitely many different outputs are possible. If a sequence $(a(n))$ is
computed by a DFAO in the following way—the input is the representation of $n$
and the output is $a(n)$—then we say $(a(n))$ is automatic. Again, a DFAO is
often displayed as a transition diagram, with the notation $q/i$ in a state
meaning that the state is numbered $q$ and has output $i$.

For example, the transition diagram in Figure 3 illustrates a DFAO computing
the sequence $(n\bmod 3)_{n\geq 0}$, where the input is in Fibonacci
representation.

Figure 3: Fibonacci DFAO computing $n\bmod 3$.

We note in passing that, due to a nice result of Charlier et al. [4], the
minimal DFAO computing $(n\bmod k)_{n\geq 0}$ for $n$ in Fibonacci
representation is known to have $2k^{2}$ states.

Finally, there is the notion of synchronized automaton that computes a
function $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$. In this case, we use a DFA,
but with two integer inputs $n$ and $x$ read in parallel, where the shorter
input is padded with leading zeros, if necessary, and the DFA accepts if and
only if $x=f(n)$. This model is suited to representing sequences of natural
numbers. It has the important advantage that if a sequence is represented in
this way, then there is a decision procedure to answer first-order queries
about the values of the sequence, in the logical structure
$\langle{\mathbb{N}},+,n\rightarrow f(n)\rangle$. See [9] for more details.

As an example, the synchronized automaton in Figure 4 computes the function
$n\rightarrow\lfloor n/2\rfloor$ in Fibonacci representation.

Figure 4: Synchronized Fibonacci automaton computing $\lfloor n/2\rfloor$.

It is quite useful to adopt the convention that in all three models, the
result is not sensitive to the presence or absence of leading zeros in the
representation of numbers.

The most powerful of all three representations for a sequence is the
synchronized automaton, since one can obtain the other two from it easily. The
downside is that it is quite possible that there exists a DFA to decide
membership in a sequence $\bf s$, but there is no corresponding synchronized
automaton computing the $n$’th term of $\bf s$.

In this paper, we sometimes use the notation called a regular expression. For
our purposes, the main thing to know is that $x^{*}$, where $x$ is a single
string or set of strings, denotes the set of all strings consisting of zero or
more concatenations of elements chosen from the set $x$ specifies. For more
about automata and regular expressions, see [6].

##  4 Walnut

Walnut is a theorem-prover for automatic sequences. It can answer first-order
queries about automatic and synchronized sequences defined over the natural
numbers ${\mathbb{N}}$. The syntax is basically first-order logic, with the
following meanings of symbols:

  * •

& is logical AND, | is logical OR, ~ is logical NOT, => is implication, and <=> means IFF.

  * •

!= means $\neq$ and x/y denotes integer division, that is, $\lfloor
x/y\rfloor$.

  * •

A is Walnut’s representation for the universal quantifier $\forall$ and E is
the representation for $\exists$.

  * •

reg defines a regular expression.

  * •

def defines an automaton for later use.

  * •

eval evaluates a first-order logic expression with no free variables, and
returns either TRUE or FALSE.

  * •

?msd_fib is a bit of jargon telling Walnut to represent all numbers in the
Fibonacci numeration system.

When Walnut returns TRUE (resp., FALSE) to an eval query, the result is a
rigorous proof that the particular logical statement holds (resp., does not
hold).

As examples, here is the Walnut code for generating the automata in Figures 2
and 4:

    def even "?msd_fib Ek n=2*k":
    def nover2 "?msd_fib z=n/2":

We will need some Walnut code for the functions $n\rightarrow\lfloor\varphi
n\rfloor$ and $n\rightarrow\lfloor\varphi^{2}n\rfloor$, where
$\varphi=(1+\sqrt{5})/2$, the golden ratio. The synchronized automata for
these can be found in [10], under the names phin and phi2n, respectively.

##  5 Guessing and checking

One of the principal tools we use is the “guess-and-check” method. Here we
guess a finite automaton computing a sequence based on empirical data, and
then use Walnut to verify that it is correct, usually by checking that the
defining equation holds. The guessing procedure is described in [10, §5.7].

We can carry out this guessing procedure for the sequence A105774, which we
call $(a(n))$. It produces a synchronized automaton that computes the sequence
in the following sense: the input is a pair $(n,x)$ in Fibonacci
representation, and the automaton accepts if and only if $x=a(n)$. The
automaton a105774 that we guess is displayed in Figure 5.

Figure 5: Synchronized Fibonacci automaton for $a(n)$.

The next step, which is crucial, is to verify that our guessed automaton is
actually correct. First we must verify that the automaton really does compute
a function. This means that for each $n$ there is exactly one $x$ such that
the pair $(n,x)$ is accepted. We can verify this as follows:

    eval check_at_least_one "?msd_fib An Ex $a105774(n,x)":
    eval check_at_most_one "?msd_fib ~En,x1,x2 x1!=x2 & $a105774(n,x1) &
       $a105774(n,x2)":

and Walnut returns TRUE for both.

Next we must verify that our automaton obeys the defining recurrence (1).

    reg adjfib msd_fib msd_fib "[0,0]*[0,1][1,0][0,0]*":
    # accepts (F_k, F_{k+1})
    def trapfib "?msd_fib $adjfib(x,y) & x<k & y>=k":
    # accepts (k,x,y) if x is the largest Fibonacci number
    # less than k and y is the next largest Fib number
    eval test105774 "?msd_fib Ak,x,y,z,t ($trapfib(k,x,y) & $a105774(k,z)
       & $a105774(k-x,t)) => y=z+t":

and Walnut returns TRUE. At this point we know that our guessed automaton is
correct.

Let’s start by proving a basic property of A105774.

######  Proposition 1.

No natural number appears three or more times in A105774.

###### Proof.

We use the following Walnut code.

    eval test012 "?msd_fib ~Ex,y,z,n x<y & y<z & $a105774(x,n) &
       $a105774(y,n) & $a105774(z,n)":

and Walnut returns TRUE. ∎

Now let’s create a DFAO computing $c(n)$, the number of times each natural
number appears in A105774. We can do this with the following Walnut commands:

    def s0 "?msd_fib ~Ex $a105774(x,n)":
    def s2 "?msd_fib Ex,y x<y & $a105774(x,n) & $a105774(y,n)":
    def s1 "?msd_fib ~($s0(n)|$s2(n))":
    combine C s1=1 s2=2 s0=0:

This creates the DFAO in Figure 6.

Figure 6: Fibonacci DFAO for $c(n)$.

The first few values of the sequence $c(n)$ are given in Table 5.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$c(n)$ | 1 | 2 | 1 | 0 | 2 | 0 | 1 | 2 | 0 | 2 | 0 | 1 | 2 | 0 | 2 | 1 | 0 | 2 | 0 | 1 | 2

It is sequence A368199 in the OEIS.

######  Proposition 2.

If $n$ appears twice in A105774, the two occurrences are consecutive.

###### Proof.

We use the following Walnut code:

    eval twice_consec "?msd_fib An,x,y (x<y & $a105774(x,n) & $a105774(y,n))
       => y=x+1":

and Walnut returns TRUE. ∎

The positions $p_{0}(n)$ of the $n$’th $0$ (respectively, the $n$’th $1$ and
the $n$’th $2$) in A368199 are also Fibonacci-synchronized. Note that we index
starting at $n=0$. Once again, we can prove this by guessing and checking. We
omit the checks that our guessed automata p0,p1,p2 compute synchronized
functions.

    eval chek1a "?msd_fib An C[n]=@1 <=> Ek $p1(k,n)":
    eval chek2a "?msd_fib An C[n]=@2 <=> Ek $p2(k,n)":
    eval chek0b "?msd_fib Aj,m,n ($p0(j,m) & $p0(j+1,n)) => m<n":
    eval chek1b "?msd_fib Aj,m,n ($p1(j,m) & $p1(j+1,n)) => m<n":
    eval chek2b "?msd_fib Aj,m,n ($p2(j,m) & $p2(j+1,n)) => m<n":

The first few values of $p_{0}$, $p_{1}$, and $p_{2}$ are given in Table 5.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$p_{0}(n)$ | 3 | 5 | 8 | 10 | 13 | 16 | 18 | 21 | 24 | 26 | 29 | 31 | 34 | 37 | 39 | 42 | 45 | 47 | 50
$p_{1}(n)$ | 0 | 2 | 6 | 11 | 15 | 19 | 23 | 28 | 32 | 36 | 40 | 44 | 49 | 53 | 57 | 61 | 66 | 70 | 74
$p_{2}(n)$ | 1 | 4 | 7 | 9 | 12 | 14 | 17 | 20 | 22 | 25 | 27 | 30 | 33 | 35 | 38 | 41 | 43 | 46 | 48

Each of these sequences is already in the OEIS. We now prove the
characterizations.

######  Proposition 3.

The numbers $p_{2}(n)$ are precisely those in A007064, that is, the natural
numbers not of the form $\lfloor\varphi k+{1\over 2}\rfloor$ for $k\geq 0$.

###### Proof.

The sequence A007067 is defined to be $\lfloor n\varphi+1/2\rfloor$. Now

$\lfloor n\varphi+1/2\rfloor=\left\lfloor{{2n\varphi+1}\over
2}\right\rfloor\\\ =\left\lfloor{{\lfloor 2n\varphi+1\rfloor}\over
2}\right\rfloor\\\ =\left\lfloor{{\lfloor 2n\varphi\rfloor+1}\over
2}\right\rfloor,$

where we have used the fact that $\lfloor{{\lfloor x\rfloor}\over
n}\rfloor=\lfloor x/n\rfloor$ for real numbers $x$ and integers $n\geq 1$.
Hence A007067 can be computed by the following Walnut code:

    def a007067 "?msd_fib Ex $phin(2*n,x) & z=(x+1)/2":

The sequence A007064 consists of those integers not in A007067. It is not hard
to see that A007064 is given (after a change of index) by $n\rightarrow\lfloor
n\varphi+\varphi/2\rfloor+n+1$ for $n\geq 0$. Indeed, we can verify this as
follows:

    def a007067 "?msd_fib Ex $phin(2*n,x) & z=(x+1)/2":
    def a007064 "?msd_fib Ex $phin(2*n+1,x) & z=n+1+x/2":
    eval check_two "?msd_fib Ax (Em $a007067(m,x)) <=> (~En $a007064(n,x))":

Finally we can prove the result about $p_{2}$ as follows:

    eval checkp2 "?msd_fib An (Ek $p2(k,n)) <=> (Em $a007064(m,n))":

and Walnut returns TRUE. ∎

######  Proposition 4.

The numbers $p_{1}(n)$, $n\geq 1$, are precisely those integers in A035487.

###### Proof.

We use the following Walnut command:

    def a035487 "?msd_fib Ex $a007064(x) & $a007067(x,n)":
    eval checkp1 "?msd_fib An (n>0) => ($a035487(n) <=> (Ek $p1(k,n)))":

and Walnut returns TRUE. ∎

Finally, we prove the result for $p_{0}$:

######  Proposition 5.

The natural numbers $p_{0}(n)$, i.e., the numbers that do not appear in
A105774 are those given by the sequence A004937, that is,
$\\{\lfloor\varphi^{2}n+{1\over 2}\rfloor\,:\,n\geq 1\\}$.

###### Proof.

We have, using the same idea as in the proof of Proposition 3, that

$\lfloor\varphi^{2}n+1/2\rfloor=\left\lfloor{{{\lfloor\varphi^{2}2n\rfloor}+1}\over
2}\right\rfloor.$

We can now use Walnut to define a synchronized automaton for A004937:

    def a004937 "?msd_fib Ex $phi2n(2*n,x) & z=(x+1)/2":

The automaton for A004937 is given in Figure 7.

Figure 7: Synchronized Fibonacci DFAO for A004937.

We can now complete the proof as follows:

    eval chk0 "?msd_fib An (n>0) => ((Ek $a004937(k,n)) <=> (Ej $p0(j,n)))":

and Walnut returns TRUE. ∎

##  6 Inequalities

######  Proposition 6.

For all $n\geq 0$ we have $\lfloor{{\varphi+2}\over 5}n\rfloor\leq
a(n)\leq\lfloor\varphi n\rfloor$.

###### Proof.

For the first inequality we write

    eval lowerbound "?msd_fib An,x,y ($a105774(n,x) & $phin(n,y)) => x>=(y+2*n)/5":

For the second inequality we use the following Walnut code:

    eval upperbound "?msd_fib An,x,y ($a105774(n,x) & $phin(n,y)) => x<=y":

and Walnut returns TRUE. ∎

The bounds in Proposition 6 are tight, as the following theorem shows.

######  Proposition 7.

We have $\liminf_{n\rightarrow\infty}a(n)/n={{\varphi+2}\over 5}$ and
$\limsup_{n\rightarrow\infty}a(n)/n=\varphi$.

###### Proof.

For the first claim, using the well-known Binet formulas for the Fibonacci and
Lucas numbers, it suffices to show that $a(L_{k}+1)=F_{k+1}+1$ for all $k\geq
3$.

    reg lucfib msd_fib msd_fib "[0,0]*[1,1][0,0][1,0][0,0]*":
    # regular expression for the pair (L_k, F_{k+1}) for k>=3
    eval chklow "?msd_fib Ax,y $lucfib(x,y) => $a105774(x+1,y+1)":

For the second result it suffices to show that $a(F_{k}+1)=F_{k+1}-1$ for all
$k\geq 2$. This follows directly from the defining recurrence for $a(n)$. Or
one can use Walnut:

    eval chkup "?msd_fib Ax,y,m ($adjfib(x,y) & $a105774(x+1,m)) => m+1=y":

∎

The graph in Figure 1 suggests studying what the positions of what might be
called “suffix minima”: those $n$ for which $a(m)>a(n)$ for all $m>n$.

######  Theorem 8.

The suffix minima of $(a(n))$ for $n>0$ occur precisely when $(n)_{F}\in
10(100^{*}10)^{*}0^{*}$.

###### Proof.

We use the following Walnut code:

    def suffmin "?msd_fib Am,x,y (m>n & $a105774(m,x) & $a105774(n,y)) => x>y":

The resulting automaton is depicted in Figure 8, from which the regular
expression is easily read off.

Figure 8: Fibonacci representation of positions of suffix minima.

∎

##  7 Consecutive identical or different terms

######  Proposition 9.

We have

  * (a)

$a(n)=a(n+1)$ if and only if $n\in\\{\lfloor\varphi^{2}k\rfloor-1\,:\,k\geq
1\\}$;

  * (b)

$a(n)\not=a(n+1)$ if and only if $n\in\\{\lfloor\varphi
k+1/\varphi\rfloor\,:\,k\geq 0\\}$.

  * (c)

$a(n)\not\in\\{a(n-1),a(n+1)\\}$ if and only if
$n\in\\{\lfloor\varphi\lfloor\varphi^{2}k\rfloor\rfloor\,:\,k\geq 1\\}$.

###### Proof.

  * (a)

We use the following Walnut command:

        eval twoconsec "?msd_fib An (Ex $a105774(n,x) & $a105774(n+1,x)) <=>
       (Ek,y (k>0) & $phi2n(k,y) & y=n+1)":

  * (b)

We use the following Walnut command:

        eval differ "?msd_fib An (Ex,y $a105774(n,x) & $a105774(n+1,y) &
       x!=y) <=> (Ek,y $phin(k+1,y) & y=n+1)":

  * (c)

We use the following Walnut commands:

        def a003623 "?msd_fib Ex $phi2n(n,x) & $phin(x,z)":
    eval isolated "?msd_fib An (n>0) => ((Ex,y,z $a105774(n-1,x) &
       $a105774(n,y) & $a105774(n+1,z) & x!=y & y!=z) <=>
       (Ek $a003623(k,n)))":

∎

The automaton computing A003623 is given in Figure 9.

Figure 9: Synchronized Fibonacci DFAO for A003623.

##  8 Sorting the terms

We can consider sorting the terms of A105774 in ascending order. The resulting
sequence is A368200. We can now guess a Fibonacci automaton for this sequence;
it is displayed in Figure 10.

Figure 10: Synchronized Fibonacci DFAO for A368200.

It now remains to verify that this is indeed A105774 in ascending order. This
is a consequence of a more general (and new) result, as follows.

######  Theorem 10.

Suppose $(a(n))_{n\geq 0}$ and $(b(n))_{n\geq 0}$ are synchronized sequences.
Then the following property is decidable: $(a(n))_{n\geq 0}$ is a permutation
of $(b(n))_{n\geq 0}$ .

###### Proof.

We just sketch the proof, which depends on linear representations. For more
about these, see [10, Chap. 9] and [2]. Given automata for $(a(n))_{n\geq 0}$
and $(b(n))_{n\geq 0}$, we can find linear representations counting the number
of occurrences of each natural number $n$ in each sequence. Then we can form
the linear representation for the difference of these two. Then we use the
fact that whether a linear representation is identically $0$ is decidable. ∎

When we perform this calculation for the sequences A105774 and A368200, we
find that the linear representation for the difference is indeed zero. It now
simply remains to check that the numbers computed by the automaton are in
ascending order:

    eval ascending "?msd_fib An,x,y ($a368200(n,x) & $a368200(n+1,y)) => y >= x":

######  Proposition 11.

Letting $b(n)=\href https://oeis.org/A368200(n)$, we have
$b(n+1)-b(n)\in\\{0,1,2\\}$.

###### Proof.

We use the following Walnut code.

    def diff "?msd_fib Ex,y $a368200(n,x) & $a368200(n+1,y) & y=x+z":
    def checkdiff "?msd_fib An,z $diff(n,z) => (z=0|z=1|z=2)":

∎

It now follows that the first difference sequence $(d(n))_{n\geq 0}$ defined
by $d(n)=b(n+1)-b(n)$ is Fibonacci-automatic. In fact, it is $c(n)$ in
disguise, as the next theorem shows.

######  Theorem 12.

For $n\geq 0$ we have $d(n)=2-c(n)$.

###### Proof.

We use the following Walnut commands:

    eval cd0 "?msd_fib An $diff(n,0) <=> C[n]=@2":
    eval cd1 "?msd_fib An $diff(n,1) <=> C[n]=@1":
    eval cd1 "?msd_fib An $diff(n,2) <=> C[n]=@0":

and Walnut returns TRUE each time. ∎

##  9 Special values

In this section we compute the values of $a(n)$ when $n$ is a Fibonacci or
Lucas number.

######  Theorem 13.

Let $s(n)=a(F_{n})$.

  * (a)

The Fibonacci representation of $s(n)$ for $n\geq 3$ is
$(1000)^{\lfloor(n-3)/4\rfloor}x_{n}$ where

$x_{n}=\begin{cases}10,&\text{if $n\equiv 0\ \mbox{\rm(mod}\
4\mbox{\rm)}$;}\\\ 101,&\text{if $n\equiv 1\ \mbox{\rm(mod}\
4\mbox{\rm)}$;}\\\ 1001,&\text{if $n\equiv 2\ \mbox{\rm(mod}\
4\mbox{\rm)}$;}\\\ 1,&\text{if $n\equiv 3\ \mbox{\rm(mod}\
4\mbox{\rm)}$.}\end{cases}$

  * (b)

$(s(n-1))$ is the OEIS sequence A006498, satisfying the recurrence
$s(n)=s(n-1)+s(n-3)+s(n-4)$ for $n\geq 4$. A closed form is as follows:

$s(n)=L_{n}/10+F_{n}/2+\begin{cases}-{1\over 5}(-1)^{n/2},&\text{$n$ even;}\\\
{2\over 5}(-1)^{(n-1)/2},&\text{$n$ odd.}\end{cases}$

###### Proof.

For part (a) we create a synchronized automaton that accepts the Fibonacci
representation of $F_{n}$, which is $10^{n-2}$, in parallel with $s(n)$. It is
displayed in Figure 11, from which the result immediately follows by
inspection.

    reg isfib msd_fib "0*10*":
    def special "?msd_fib $isfib(x) & $a105774(x,y)":

Figure 11: Synchronized Fibonacci DFAO for $s(n)$.

For part (b) we first create a DFA that accepts, in parallel, the Fibonacci
representations of $F_{n+4},F_{n+3},F_{n+1},F_{n}$. Then we check the
recurrence.

    reg four msd_fib msd_fib msd_fib msd_fib
       "[0,0,0,0]*[1,0,0,0][0,1,0,0][0,0,0,0][0,0,1,0][0,0,0,1][0,0,0,0]*":
    eval partb "?msd_fib Aa,b,c,d,x,y,z,w ($four(a,b,c,d) & $a105774(a,x) &
       $a105774(b,y) & $a105774(c,z) & $a105774(d,w)) => x=y+z+w":

and Walnut returns TRUE. ∎

######  Proposition 14.

  * (a)

Suppose $k\geq 3$. Over the range $F_{k}\leq n<F_{k+1}$, the sequence $a(n)$
achieves its minimum uniquely at $n=F_{k}$.

  * (b)

Suppose $k\geq 5$. Over the range $F_{k}\leq n<F_{k+1}$, the sequence $a(n)$
achieves its maximum only at $n=F_{k}+1$ and $n=F_{k}+2$.

###### Proof.

We use the following Walnut code:

    eval minval "?msd_fib Ax,y,z,t,u ($adjfib(x,y) & $a105774(x,z) &
       t>x & t<y & $a105774(t,u)) => u>z":
    eval maxval "?msd_fib Ax,y,z,t,u,w (x>=5 & $adjfib(x,y) & $a105774(x+1,z) &
    $a105774(x+2,w) & t>=x & t<y & $a105774(t,u)) => (z=w & u<=z)":

and Walnut returns TRUE for both. ∎

######  Corollary 15.

Suppose $F_{k}\leq n<F_{k+1}$. Then $s(k)\leq a(n)\leq F_{k+1}-1$.

######  Theorem 16.

Define $t(n)=a(L_{n})$ for $n\geq 0$. Then $t(n)=t(n-1)+t(n-3)+t(n-4)$ for
$n\geq 5$. A closed form for $n\geq 2$ is given by

$t(n)=3L_{n}/10+3F_{n}/2+\begin{cases}{2\over 5}(-1)^{n/2},&\text{$n$
even;}\\\ {1\over 5}(-1)^{(n-1)/2},&\text{$n$ odd.}\end{cases}$

###### Proof.

Same ideas as in Theorem 13. We omit the details. ∎

##  10 Parity

######  Proposition 17.

We have $a(n)\equiv\lfloor n\varphi\rfloor\ \mbox{\rm(mod}\ 2\mbox{\rm)}$ for
$n\geq 0$.

###### Proof.

We use the following Walnut code:

    def even "?msd_fib Ek n=2*k":
    eval checkparity "?msd_fib An,x,y ($a105774(n,x) & $phin(n,y)) =>
       ($even(x) <=> $even(y))":

and Walnut returns TRUE. ∎

##  11 Distinct values

Given a sequence taking values in ${\mathbb{N}}$ we can consider the same
sequence obtained by scanning the terms from left-to-right, and deleting any
values that previous occurred in the sequence. We call this the distinctness
transform of the original sequence. For example, the distinctness transform of
A105774 starts $0,1,2,4,7,6,12,11,\ldots$. We have the following new theorem.

######  Theorem 18.

The following problem is decidable: given two synchronized automata computing
$s(n)$ and $s^{\prime}(n)$, whether $(s^{\prime}(n))$ is the distinctness
transform of $(s(n))$.

###### Proof.

It suffices to create a first-order logical formula asserting that
$(s^{\prime}(n))$ is the distinctness transform of $(s(n))$.

This formula asserts

  * (a)

An integer occurs in the range of $s(n)$ iff it occurs in the range of
$s^{\prime}(n)$;

  * (b)

All the values $s^{\prime}(n)$ for $n\geq 0$ are distinct;

  * (c)

For all $x$ and $y$, if $x$’s first occurrence in $(s(n))$ precedes that of
$y$’s first occurrence, then $x$’s unique occurrence in $(s^{\prime}(n))$ also
precedes that of $y$.

∎

Let us carry this out for A105774. Let $(a^{\prime}(n))$ denote the
distinctness transform of $(a(n))$. The first few values are given in Table
11.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$a^{\prime}(n)$ | 0 | 1 | 2 | 4 | 7 | 6 | 12 | 11 | 9 | 20 | 19 | 17 | 14 | 15 | 33 | 32 | 30 | 27 | 28 | 22

We can guess the automaton for this sequence and then verify it.

Figure 12: Synchronized Fibonacci automaton for $a^{\prime}(n)$.

First let us check that our guessed automaton really does compute a function:

    def checkap1 "?msd_fib An Ex $aprime(n,x)":
    def checkap2 "?msd_fib ~En,x1,x2 x1!=x2 & $aprime(n,x1) & $aprime(n,x2)":

and Walnut returns TRUE for both.

Next, let’s check the three conditions guaranteeing that $a^{\prime}$ is the
distinctness transform of $a$:

    eval check_distinct1 "?msd_fib Ax (Em $a105774(m,x)) <=> (En $aprime(n,x))":
    eval check_distinct2 "?msd_fib ~En1,n2,x n1!=n2 & $aprime(n1,x) &
       $aprime(n2,x)":
    def first_occ "?msd_fib $a105774(y,n) & Ax (x<y) => ~$a105774(x,n)":
    # provided n occurs in A105774, gives the least position y
    # where it occurs
    eval check_distinct3 "?msd_fib Ax,y,i,j ($first_occ(x,i) & $first_occ(y,j)
       & i<j) => Em,n $aprime(m,x) & $aprime(n,y) & m<n":

and Walnut returns TRUE for all of them.

We now examine the run-length encoding of A105774. The run-length encoding of
an arbitrary sequence $(s(n))_{n\geq 0}$ counts the size of maximal blocks of
consecutive identical values [5]. For A105774 it is
$1,2,1,2,2,1,2,1,2,\ldots$.

Once we have the distinct terms of A105774, we can easily determine the run-
length encoding of the sequence.

######  Theorem 19.

The run-length encoding of A105774 is A001468, that is,

$1(2-{\bf f}[0])(2-{\bf f}[1])(2-{\bf f}[2])\cdots$

where ${\bf f}=01001\cdots$ is the infinite Fibonacci word [1].

###### Proof.

The claim can be verified by the following Walnut code:

    def nthrun2 "?msd_fib Ex,y $aprime(n,x) & $first_occ(x,y) &
       $a105774(y+1,x)":
    eval compare_fib "?msd_fib An $nthrun2(n+1) <=> F[n]=@0":

∎

##  12 Other results

Define $w(n)$ to be the least integer such that $a(w(n))\geq n$. The first few
terms of this sequence are given in Table 12.

$n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$w(n)$ | 0 | 1 | 3 | 4 | 4 | 6 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 14 | 14 | 14 | 14 | 14 | 14 | 14 | 14

######  Proposition 20.

If $n\geq 2$ and $F_{k}\leq n<F_{k+1}$ then $w(n)=F_{k}+1$.

###### Proof.

We use the following Walnut commands:

    def trapfib2 "?msd_fib $adjfib(x,y) & x<=k & y>k":
    def wseq "?msd_fib (Em $a105774(x,m) & m>=n) &
       (Ai,p (i<x & $a105774(i,p)) => p<n)":
    eval propw "?msd_fib Ax,y,n,m (n>=2 & $trapfib2(n,x,y) & $wseq(n,m))
       => m=x+1":

and Walnut returns TRUE. ∎

We now turn to describing the fixed points of $a$.

######  Theorem 21.

We have $a(n)=n$ for $n>0$ if and only if $(n)_{F}\in
1(00100^{*}1)^{*}\\{\epsilon,01,010,0100\\}$.

###### Proof.

We use the Walnut command

    def fixed "?msd_fib $a105774(n,n)":

and it produces the automaton in Figure 13, from which we can directly read
off the result.

Figure 13: Solutions to $a(n)=n$.

∎

For the remainder of this section, let $a(n)$ represent (as before) the $n$’th
term of A105774, let $b(n)=\lfloor n\varphi\rfloor$, and let $c(n)=\lfloor
n\varphi^{2}+1/2\rfloor$. We will find some relations concerning the
composition of the functions $a$, $b$, and $c$. We introduce the function
$x(n):=a(b(n))-b(a(n))$.

######  Theorem 22.

  * (a)

$a(b(n))\geq b(a(n))$ for all $n\geq 0$.

  * (b)

For $n\geq 1$, the difference $x(n):=a(b(n))-b(a(n))$ is exactly the parity of
the number of $1$’s in the Fibonacci representation of $n-1$, that is,
sequence A095076.

  * (c)

$b(a(b(n)))\geq a(b(a(n)))$ for all $n\geq 0$.

  * (d)

$a(a(b(n)))-a(b(a(n)))\in\\{-2,0,2\\}$ for all $n\geq 0$.

  * (e)

If $d(n):=c(a(n))-a(b(n))-a(n)$, then $d(n)\in\\{-1,0,1\\}$ for all $n\geq 0$.

  * (f)

For $n\geq 1$ we have $d(n)=0$ iff ${\bf f}[n-1]=1$.

  * (g)

For $n\geq 1$ we have $c(a(b(n)))+a(b(n))-a(b(b(n)))-2b(a(n))=1$.

###### Proof.

We use the following Walnut commands:

    reg even1 msd_fib "(0*10*1)*0*":
    # even number of 1’s in Fibonacci representation

    def ab "?msd_fib Ex $phin(n,x) & $a105774(x,z)":
    # z = a105774(floor(phi*n))

    def ba "?msd_fib Ex $a105774(n,x) & $phin(x,z)":
    # z = floor(phi*a105774(n))

    # check that ab >= ba for all n so subtraction makes sense over N:
    def test "?msd_fib An,x,y ($ab(n,x) & $ba(n,y)) => x>=y":
    # Walnut says TRUE

    def xx "?msd_fib Ex,y $ab(n,x) & $ba(n,y) & z=x-y":
    # 12 states

    #test that a(b(n)) = b(a(n)) precisely when parity of 1’s in
    #Fibonacci expansion of n-1 is 0:

    eval test1 "?msd_fib An $xx(n+1,0) <=> $even1(n)":
    # Walnut says TRUE
    #so it follows immediately
    # that a(b(n)) > b(a(n)) precisely when parity of 1’s in
    #Fibonacci expansion of n-1 is 1, no need to test it

    def aba "?msd_fib Ex $ba(n,x) & $a105774(x,z)":
    # 38 states
    def bab "?msd_fib Ex $ab(n,x) & $phin(x,z)":
    # 18 states

    # check the inequality bab(n) >= aba(n):
    eval test3 "?msd_fib An,x,y ($bab(n,x) & $aba(n,y)) => x>=y":
    # Walnut says true

    def aab "?msd_fib Ex $ab(n,x) & $a105774(x,z)":
    # 34 states

    # check the proposition that aab(n) - aba(n) takes values in
    # {-2,0,2} only:
    eval test4 "?msd_fib An,x,y ($aab(n,x) & $aba(n,y)) => (x=y|x=y+2|y=x+2)":
    # Walnut says TRUE

    def a004937 "?msd_fib Ex $phi2n(2*n,x) & z=(x+1)/2":
    def ca "?msd_fib Ex $a105774(n,x) & $a004937(x,z)":
    def dp "?msd_fib Ew,x,y $ca(n,w) & $ab(n,x) & $a105774(n,y) & z+x+y=w+1":
    # here dp computes d(n)+1
    eval test1 "?msd_fib An,x $dp(n,x) => (x=0|x=1|x=2)":
    eval test2 "?msd_fib An (n>=1) => (F[n-1]=@1 <=> $dp(n,1))":

    def cab "?msd_fib Ex $ab(n,x) & $a004937(x,z)":
    def abb "?msd_fib Ex $phin(n,x) & $ab(x,z)":
    eval test3 "?msd_fib An,r,s,t,u (n>=1 & $cab(n,r) & $abb(n,s) & $ab(n,t)
       & $ba(n,u)) => r+t=s+2*u+1":

∎

##  13 Carlitz-style results

In a classic paper [3], Carlitz et al. obtained results involving compositions
of the functions $b(n)=\lfloor\varphi n\rfloor$ and
$d(n)=\lfloor\varphi^{2}n\rfloor$. We can obtain a version of their Theorem
13, involving $a(n)=\href https://oeis.org/A105774(n)$, as follows:111We warn
the reader that our $b(n)$ is written as $a(n)$ in the paper of Carlitz et
al., and our $d(n)$ is their $b(n)$.

We adopt the following notation: if $u=u_{1}\cdots u_{t}\in\\{a,b,d,x\\}^{*}$,
then by $u(n)$ we mean $(u_{1}\circ\cdots\circ u_{t})(n)$. Recall that $x$ was
defined in Section 12.

######  Theorem 23.

Let $u\in\\{b,d\\}^{+}$ be a nonempty word with $i$ copies of $b$ and $j$
copies of $d$. Then for all $n\geq 1$ we have

$au(n)=F_{i+2j}\cdot ab(n)+F_{i+2j-1}\cdot a(n)+C(u)\cdot(2x(n)-1),$

where $C(u)$ is defined as follows:

$C(u)=\begin{cases}0,&\text{if $u=b$};\\\ 1,&\text{if $u=d$};\\\
F_{i+2j-1}+C(v),&\text{if $u=vb$};\\\ F_{i+2j-1}-C(v),&\text{if
$u=vd$}.\end{cases}$ (4)

###### Proof.

First we need some lemmas:

######  Lemma 24.

We have

  * (a)

$xb(n)=x(n)$ for all $n\geq 0$.

  * (b)

$xd(n)=1-x(n)$ for all $n\geq 1$.

  * (c)

$abb(n)=ab(n)+a(n)+2x(n)-1$ for all $n\geq 1$.

  * (d)

$abb(n)=ad(n)$ for all $n\geq 0$.

  * (e)

$abd(n)=2ab(n)+a(n)+2x(n)-1$ for all $n\geq 1$.

###### Proof.

These can be proved with Walnut as follows. Recall that phin is Walnut’s name
for $b$ and phi2n is Walnut’s name for $d$.

    eval checka "?msd_fib An,y,z,w (n>=0 & $xx(n,y) & $phin(n,z) & $xx(z,w))
       => w=y":
    eval checkb "?msd_fib An,y,z,w (n>=1 & $xx(n,y) & $phi2n(n,z) & $xx(z,w))
       => w+y=1":
    eval checkc "?msd_fib An,y,z,w,t (n>=1 & $abb(n,y) & $ab(n,z) &
       $a105774(n,w) & $xx(n,t)) => y+1=z+w+2*t":
    def ad "?msd_fib Ew $phi2n(n,w) & $a105774(w,z)":
    def abd "?msd_fib Ew,y $phi2n(n,w) & $phin(w,y) & $a105774(y,z)":
    eval checkd "?msd_fib An,z (n>=0 & $ad(n,z)) => $abb(n,z)":
    eval checke "?msd_fib An,y,z,w,t (n>=1 & $abd(n,y) & $ab(n,z) &
       $a105774(n,w) & $xx(n,t)) => y+1=2*z+w+2*t":

and Walnut returns TRUE for all. ∎

Now we can prove the desired result by induction on $|u|$. It is clear from
the above results for $|u|=1$. Now assume $|u|\geq 2$ and consider two cases:
$u=vb$ and $u=vd$.

$u=vb$: In this case we have, by induction, that

$av(n)=F_{i+2j-1}\cdot ab(n)+F_{i+2j-2}\cdot a(n)+C(v)\cdot(2x(n)-1).$

Substituting $b(n)$ for $n$, we get

$\displaystyle avb(n)$ $\displaystyle=F_{i+2j-1}\cdot abb(n)+F_{i+2j-2}\cdot
ab(n)+C(v)\cdot(2xb(n)-1)$
$\displaystyle=F_{i+2j-1}\cdot(ab(n)+a(n)+2x(n)-1)+F_{i+2j-2}ab(n)+C(v)\cdot(2xb(n)-1)$
$\displaystyle=F_{i+2j}\cdot ab(n)+F_{i+2j-1}a(n)+(C(v)+F_{i+2j-1})(2x(n)-1),$

as desired.

$u=vd$: By induction we have

$av(n)=F_{i+2j-2}\cdot ab(n)+F_{i+2j-3}\cdot a(n)+C(v)\cdot(2x(n)-1).$

Substituting $d(n)$ for $n$, we get

$\displaystyle avd(n)$ $\displaystyle=F_{i+2j-2}\cdot abd(n)+F_{i+2j-3}\cdot
ad(n)+C(v)\cdot(2xd(n)-1)$
$\displaystyle=F_{i+2j-2}\cdot(2ab(n)+a(n)+2x(n)-1)+F_{i+2j-3}(ab(n)+a(n)+2x(n)-1)$
$\displaystyle\quad+C(v)(2(1-x(n))-1)$ $\displaystyle=F_{i+2j}\cdot
ab(n)+F_{i+2j-1}a(n)+(F_{i+2j-1}-C(v))(2x(n)-1).$

This completes the proof. ∎

We can obtain a linear representation for $C(u)$, as follows.

######  Corollary 25.

Define vectors $L,R$ and a matrix-valued morphism $\mu$ as follows:

$\displaystyle L$
$\displaystyle=\left[\begin{array}[]{ccc}0&0&1\end{array}\right]$
$\displaystyle\mu(b)$ $\displaystyle=\left[\begin{array}[]{ccc}0&1&0\\\
1&1&0\\\ 0&1&1\end{array}\right]$ $\displaystyle\mu(d)$
$\displaystyle=\left[\begin{array}[]{ccc}0&0&1\\\ 0&1&1\\\
1&2&1\end{array}\right]$ $\displaystyle R$
$\displaystyle=\left[\begin{array}[]{c}1\\\ 0\\\ 0\\\ \end{array}\right].$

Then $C(u)=L\mu(u)R$.

###### Proof.

We first obtain the following relations, for $v\in\\{b,d\\}^{+}$:

$\displaystyle C(vbb)$ $\displaystyle=C(v)+C(vb)+C(vd)$ $\displaystyle C(vbd)$
$\displaystyle=C(vd)$ $\displaystyle C(vdb)$ $\displaystyle=C(vb)+2C(vd)$
$\displaystyle C(vdd)$ $\displaystyle=C(v)+C(vb)+C(vd).$

We just show how to obtain the first relation; the others are similar. Letting
$u=vbb$, and using (4), we get

$\displaystyle C(u)$ $\displaystyle=C(vbb)=F_{i+2j-1}+C(vb)$ $\displaystyle
C(vb)$ $\displaystyle=F_{i+2j-2}+C(v)$

from which it follows that $C(u)=F_{i+2j}+C(v)$. On the other hand, from (4),
we have $C(vd)=F_{i+2j-1}-C(v)$ and so

$C(v)+C(vb)+C(vd)=C(v)+F_{i+2j-2}+C(v)+F_{i+2j-1}-C(v)=C(v)+F_{i+2j},$

and the first identity follows.

Once we have the relations, we can combine them in the usual way to obtain the
given linear representation. ∎

##  14 Going further

It is possible to study many similar recurrences using exactly the same
techniques. We list just three possibilities; many more should occur to the
interested reader.

  1. 1.

One can study a variation of the defining recurrence (1) where the Lucas
numbers replace the Fibonacci numbers. The resulting sequence is A118287 in
the OEIS, and is computed by a $102$-state synchronized automaton.

With this automaton one can easily prove observations such as

A118287$(n)$ = A118287$(n-2)$ if and only if $n$ belongs to A003231.

  2. 2.

One can generalize (1) by introducing two integer parameters, $x$ and $y$, as
follows:

$a_{x,y}(n)=\begin{cases}n,&\text{if $n\leq 1$};\\\
F_{j+1}x-a_{x,y}(n-F_{j})y,&\text{if $F_{j}<n\leq F_{j+1}$ for $j\geq
2$}.\end{cases}$ (5)

Equation (1) corresponds to $(x,y)=(1,1)$. Numerical experiments suggest that
if $y=1$, the resulting sequence might be Fibonacci-synchronized for each
$x\geq 1$.

     * •

Consider the particular case $(x,y)=(2,1)$. Then one can prove that
$a_{2,1}(n)$ is computed by a $22$-state synchronized automaton. Furthermore,
$((a_{2,1}(n)-1)/2)_{n\geq 1}$ is sequence A343647 and is a permutation of the
positive integers.

     * •

The case $(x,y)=(3,2)$ seems harder to analyze. It is quite possible that it
is not Fibonacci-synchronized.

  3. 3.

Another variation is the following:

$b(n)=\begin{cases}n,&\text{if $n\leq 1$};\\\ F_{j+1}-b(b(n-F_{j})),&\text{if
$F_{j}<n\leq F_{j+1}$ for $j\geq 2$}.\end{cases}$ (6)

This sequence is generated by a $24$-state synchronized automaton.

## References

  * [1] J. Berstel.  Fibonacci words—a survey.  In G. Rozenberg and A. Salomaa, editors, The Book of L, pp. 13–27. Springer-Verlag, 1986.
  * [2] J. Berstel and C. Reutenauer.  Noncommutative Rational Series With Applications, Vol. 137 of Encyclopedia of Mathematics and Its Applications.  Cambridge University Press, 2011.
  * [3] L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr.  Fibonacci representations.  Fibonacci Quart. 10 (1972), 1–28.
  * [4] É. Charlier, N. Rampersad, M. Rigo, and L. Waxweiler.  The minimal automaton recognizing $m{\mathbb{N}}$ in a linear numeration system.  INTEGERS 11B (2011), Paper #A4.
  * [5] S. W. Golomb.  Problem 5407.  Amer. Math. Monthly 73 (1966), 674.  Solution by D. Marcus and N. J. Fine, 74 (1967), 740–743.
  * [6] J. E. Hopcroft and J. D. Ullman.  Introduction to Automata Theory, Languages, and Computation.  Addison-Wesley, 1979.
  * [7] C. G. Lekkerkerker.  Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci.  Simon Stevin 29 (1952), 190–195.
  * [8] H. Mousavi.  Automatic theorem proving in Walnut.  Arxiv preprint arXiv:1603.06017 [cs.FL], available at http://arxiv.org/abs/1603.06017, 2016.
  * [9] J. Shallit.  Synchronized sequences.  In T. Lecroq and S. Puzynina, editors, WORDS 2021, Vol. 12847 of Lecture Notes in Computer Science, pp. 1–19. Springer-Verlag, 2021\.
  * [10] J. Shallit.  The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words with Walnut, Vol. 482 of London Math. Soc. Lecture Note Series.  Cambridge University Press, 2022.
  * [11] N. J. A. Sloane et al.  The on-line encyclopedia of integer sequences, 2023.  Available at https://oeis.org.
  * [12] E. Zeckendorf.  Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas.  Bull. Soc. Roy. Liège 41 (1972), 179–182.