Appellant Donald Ben Bartsma pleaded guilty to one count of possession of a firearm by a convicted felon in violation of 18 U.S.C. § 922(g)(1) and was sentenced to fifty-eight months imprisonment. In arriving at the • final sentence, the district court departed upward from the otherwise applicable Guideline range pursuant to United States Sentencing Guideline 4A1.3. The district court also imposed a special condition of supervised release requiring Mr. Bartsma to register as a “sex offender” in any state in which he resides after his release from prison. Mr. Bartsma now appeals, challenging the district court’s upward departure, the special condition of supervised release, and also claiming he was entitled to presentence notice of the court’s intention to consider imposing sex offender registration as a special condition of supervised release. We exercise jurisdiction pursuant to 28 U.S.C. § 1291 and 18 U.S.C. § 3742. We affirm in part, reverse in part, and remand for resentenc-ing.
BACKGROUND
Mr. Bartsma’s appeal focuses exclusively on the propriety of his sentence and conditional release. As such, we only briefly discuss the facts. On July 20, 1998, Mr. Bartsma pleaded guilty to one count of possession of a firearm by a convicted felon in violation of 18 U.S.C. § 922(g)(1). 1 The Presentence Investigation Report listed Mr. Bartsma’s base offense level at 20, as prescribed in U.S.S.G. § 2K2.1(a)(4)(A). A three-level downward adjustment was recommended for acceptance of responsibility under U.S.S.G. § 3E1.1(a) and (b) to reach a total offense level of 17. When the offense level was cross-referenced with the applicable criminal history category of IV, 2 Mr. Bartsma’s Guideline range stood at thirty-seven to forty-six months.
At the sentencing hearing the district court determined the criminal history category of IV did not adequately reflect either the seriousness of Mr. Bartsma’s past criminal conduct, or the likelihood he would commit other crimes. Accordingly, the district court imposed an upward departure to category VI, and sentenced Mr. Bartsma to fifty-eight months imprisonment. The district court also sentenced Mr. Bartsma to three years of supervised release, and as a condition of the release required him to register as a sex offender in any state in which he resides. The district court justified the upward departure and the registration requirement by citing: (1) the nature of Mr. Bartsma’s prior offenses, which include child molestation and rape; (2) Mr. Bartsma’s history of prompt recidivism after being released for prior offenses; and (3) California’s refusal to grant Mr. Bartsma parole on several occasions because he was viewed as a danger to the community.
Mr. Bartsma asserts several errors: (1) the district court abused its discretion by imposing the upward departure; (2) the district court failed to notify Mr. Bartsma it was considering imposing a sex offender registration requirement as a condition of *1195 supervised release; and (3) the district court abused its discretion by imposing the sex offender registration requirement as a condition of supervised release because the condition (sex offender registration) was not reasonably related to the nature or circumstances of the offense charged (possession of a firearm by a felon).
DISCUSSION
I. The Upward Departure
The analysis we use when reviewing Sentencing Guideline departures is well settled, and need not be spelled out exhaustively here. Following the Supreme Court’s seminal case of
Koon v. United States,
In reviewing a departure from the Guidelines, we must evaluate:
(1) whether the factual circumstances supporting a departure are permissible departure factors; (2) whether the departure factors relied upon by the district court remove the defendant from the applicable Guideline heartland thus warranting a departure; (3) whether the record sufficiently supports the factual basis underlying the departure; and (4) whether the degree of departure is reasonable.
Collins,
As we stated earlier, the district court departed upward from the applicable criminal history category of IV to a category of VI. The Sentencing Guidelines specifically encourage an upward departure when the district court concludes “the criminal history category does not adequately reflect the seriousness of the defendant’s past criminal conduct or the likelihood that the defendant will commit other crimes.” U.S.S.G. § 4A1.3. Because § 4A1.3 provides an encouraged basis for departure, we find the district court relied on permissible departure factors when imposing the upward departure.
See Collins,
While conceding § 4A1.3 permits an upward departure for an under-represented criminal history category, Mr. Bartsma focuses on the last three steps of the Collins inquiry and contends the facts of this case are insufficient to remove him from the heartland of criminal history category IV, the record is insufficient to support the factual basis underlying the departure, and the departure was not reasonable. After reviewing the record before us, we conclude the district court did not abuse its discretion in deciding to depart upward. *1196 However, the district court failed to articulate sufficient findings to support the degree of the departure, and therefore we remand for resentencing.
The district court based its departure on Mr. Bartsma’s “extensive criminal record involving repeated crimes of violence,” and its determination he was “a repeat criminal who repeats ... quickly after his release into the community.” The court also noted “the prison records received from California Department of Corrections reveal the defendant was not granted parole on several occasions because he was viewed as a danger to the community.” The Presentence Investigation Report, which the district court adopted, supports these conclusions. Specifically, the report noted Mr. Bartsma had several juvenile adjudications, including a charge of child molestation and a charge of unlawful sexual intercourse with a minor, which went uncounted for the purposes of criminal history. In addition, Mr. Bartsma had shown an inability to stay out of trouble — he was arrested on the sexual intercourse with a minor charge just two months after jurisdiction in the child molestation case terminated; he committed rape by force four months after being paroled from the confinement sentence he received for the sexual intercourse with a minor charge; he was arrested in the current case four months after serving his sentence on the rape charge.
3
Finally, California Department of Corrections records indicated Mr. Bartsma had poor impulse control, sadistic impulses toward women, and had fantasies that included raping and torturing a woman. Given the record as a whole, and recognizing the district court’s special competence in determining the unusualness of a case,
see Collins,
Having upheld the district court’s determination to depart upward, we now consider whether the extent of the departure — from a category IV to a category VI — was reasonable. Our review of the reasonableness of a district court’s departure is deferential.
See Whiteskunk,
In the present case, the district court offered little more than conclusory statements in support of its degree of departure. In its Memorandum and Order ruling on Mr. Bartsma’s objections to the *1197 Presentence Report, the district court stated:
Based on the materials in the Presen-tence Report, the court concludes that the defendant’s criminal history category of IV significantly under represents the seriousness of his prior criminal conduct and the likelihood that he will commit other crimes. [The court then lists the aforementioned factors used to justify the upward departure.] Under the circumstances, the court concludes that a criminal history category of VI more accurately reflects the seriousness of the defendant’s criminal history and the likelihood of future crimes.
The district court made a similar oral ruling during the sentencing hearing. The district court’s statements mirror similar justifications we have held in the past to be insufficiently particular to support a degree of departure.
See Whiteskunk,
As was the case in
Whiteskunk,
we find nothing in the record, the presentence report, or the sentencing transcript which provides any explanation or methodological basis for how the district court arrived at an upward departure of two criminal history categories.
Id.
We often have stated the district court is not required to justify the degree of departure with mathematical precision, but the court is required to include in its justification “some method of analogy, extrapolation or reference to the sentencing guidelines.”
United States v. O’Dell,
Given our inability to determine whether the degree of departure was reasonable, we must remand for resentencing. Mindful of the multitude of tasks required of our district courts at sentencing, we nevertheless again implore them to precisely lay out their reasoning and analysis as to why they selected a particular degree of departure.
II. The Special Condition of Supervised Release — Sex-Offender Registration
Mr. Bartsma’s final two arguments center around the district court’s imposition of the special condition of supervised release requiring him to register as a sex offender. First, Mr. Bartsma contends he was entitled, as a matter of law, to presentence notice the condition was under consideration. Second, Mr. Bartsma argues the district court erred by imposing the condition because there was no reasonable relationship between the condition and the crime of possession of a firearm by a felon. We review conditions of supervised release for abuse of discretion.
United States v. Edgin,
Before deciding whether presen-tence notice was required, we first must determine whether Mr. Bartsma preserved the issue for appeal. The Government argues defense counsel failed to object to the condition, or the lack of notice, and therefore our review should be for plain
*1198
error.
See United States v. Fabiano,
In
Edgin,
the district court imposed a special condition of release that prevented Mr. Edgin from contacting his son.
Edgin,
We now turn to the question of whether Mr. Bartsma was entitled to notice before the district court imposed the special condition ordering him to register as a sex offender. Having found no controlling authority directly on point, we analyze this issue as one of first impression. The only other Circuit to decide the issue applied Rule 32 and the Supreme Court’s decision in
Bums
to hold reasonable pre-sentence notice was required.
See Coe-nen,
In
Bums,
the Supreme Court held Rule 32 required reasonable notice to the parties when a district court is contemplating an upward departure based on a ground not listed in either the presentence report or a prehearing submission by the Government.
Burns,
We find further support for our position in the statutes. 18 U.S.C. § 3555 allows a district court to order defendants convicted of offenses involving fraud or other intentionally deceptive practices to notify their victims of the existence and nature of their conviction. When a district court plans to order notice pursuant to § 3555, presentence notice to the parties is required: “Prior to imposing an order of notice pursuant to section 3555, the court shall give notice to the defendant and the Government that it is considering imposing such an order.” 18 U.S.C. § 3553(d); see
also Coenen,
We conclude Mr. Bartsma was entitled to receive reasonable presentence notice, either from the Presentence Report, a pre-hearing submission from the Government, or the district court itself, that a special condition of supervised release requiring him to register as a sex offender was a possibility. 7 Mr. Bartsma is obviously on notice now, and all parties should be prepared to address this issue on remand.
Having determined Mr. Bartsma was entitled to notice, we do not reach the issue of whether the district court abused its discretion by imposing the sex offender registration requirement in this case. We do note the record before us is void of any findings or a determination by the district court that the special condition was reasonably related to the current offense. District courts enjoy broad discretion in fashioning conditions of supervised release.
Edgin,
“involve no greater deprivation of liberty than is reasonably necessary” to deter criminal conduct, protect the public, and provide the defendant with needed educational or vocational training, medical care, or other correctional treatment. ... [T]he conditions must [also] be “reasonably related” to “the nature and circumstances of the offense and the history and characteristics of the defendant.”
Fabiano,
In conclusion, we hold the district court did not abuse its discretion by imposing an upward departure from the Sentencing Guidelines. The record is clearly sufficient to support such a decision. Howev *1201 er, the district court failed to adequately justify the degree of departure. In addition, Mr. Bartsma was entitled to presen-tence notice the district court was considering imposing a sex offender registration requirement as a special condition of supervised release. Therefore, we remand for resentencing with instructions to the district court to provide sufficient findings in support of the methodology used to determine the degree of departure. Remand is necessary also to afford Mr. Bartsma the presentence notice he is entitled to, and will allow both parties the opportunity to argue the propriety and the practicalities of sex offender registration in this case.
Accordingly, we AFFIRM the district court’s upward departure, VACATE the sentence, and REMAND to the district court for resentencing in a manner consistent with this opinion.
Notes
. Mr. Bartsma’s previous felony conviction was for rape by force. The California court in that case sentenced Mr. Bartsma to a prison term of nine years, which he served in its entirety.
. The probation officer who prepared the Pre-sentence Investigation Report assessed Mr. Bartsma three criminal history points for his rape conviction, three points for a conviction of possession of a concealed weapon while in prison, and two additional points pursuant to U.S.S.G. § 4A1.1(e) because Mr. Bartsma committed the instant offense less than two years after his release from prison in the rape case. Thus, the Report assessed Mr. Bartsma a total of eight criminal history points. (ROA, Vol. III, P.I.R. at 8-9, ¶¶ 32-34.)
. The last incident of recidivism cannot be a basis for enhancement on its own because two additional points were already added to Mr. Bartsma's criminal history score pursuant to U.S.S.G. § 4Al.l(e). See supra note 2.
. In
United States v. Coenen,
At the sentencing hearing in the present case, defense counsel was clearly caught off-guard by the imposition of the special condition, to the point he was unable to make a reasoned argument against the condition. Counsel clearly had some concerns about the condition; however the exchange with the court ended too abruptly for those concerns to be fully developed:
[COUNSEL]: Your Honor, a couple other matters. The Court did mention that you were going to require him to register as a sex offender wherever he resides when he is finally released from prison. Would it be the Court's order that he register according to whatever law that state has? Because I think practically all the states has [sic] them now, sex offender registers.
THE COURT: My ruling is just what it says; wherever he goes he's to be registered.
[COUNSEL]: Even if the law doesn’t require him—
THE COURT: If the law doesn't require it. As far as I’m concerned, when I say so, the law requires it when I say so.
. Rule 32(c)(1) states in part: "At the sentencing hearing, the court must afford counsel for the defendant and for the Government an opportunity to comment on the probation officer’s determinations and on other matters relating to the appropriate sentence.” Fed. R.Crim.P. 32(c)(1).
. The case before us perfectly illustrates the reason for the Court's sentiment. Neither party had any inkling the district court was considering imposing the sex offender registration requirement, so both sides were utterly unprepared to make reasoned arguments to the court. Counsel for the Government conceded at oral argument he was completely surprised by the registration requirement, he had not even considered it as an option, and he would have liked to have had some advance notice. As stated earlier, defense counsel was obviously taken aback. Moreover, this was not a case where the special condition imposed shared an obvious nexus with the crime charged. In fact, when Mr. Barts-ma first arrived in Kansas after having been released from prison, he apparently tried to register as a sex offender and was told he did not need to register under Kansas law. It strains credulity to argue Mr. Bartsma should have known registration was a possibility after his possession of a gun conviction when he had already been told his history as a rapist did not require it. Had the district court given the parties notice, they could have briefed the propriety of the condition, as well as the practical application. An intelligent, adversarial argument would have helped the court flesh out the problems with the current order. Without such an opportunity, we are left with an almost bare record telling us Mr. Bartsma is required to "register as a sex offender,” with absolutely no guidance as to what that actually means. Nor do we have the ability on review to properly determine whether the sex offender registration requirement was reasonably related to the current offense because the district court did not make findings to that effect. Notice to the parties could have solved these deficiencies.
. We do not create a rule today requiring notice prior to the imposition of every special condition of supervised release.
See United States
v.
Warren,
